Кинозал

Однажды Вася пришёл в известный кинотеатр «Прямая», чтобы посмотреть новый боевик. Когда он проходил к своему месту в зале, то ему пришлось потревожить некоторых людей, которые заняли свои места раньше него. Он был этим так расстроен, что решил в следующий раз заранее определить минимальное количество людей, которым он должен помешать.

Известно, что кинозал имеет форму прямоугольника шириной W (количество мест в ряду) и высотой H (количество рядов). Каждая клетка внутри прямоугольника задаётся координатами (a, b) так, что 1 ≤ a ≤ H и 1 ≤ b ≤ W. Клетка может быть либо местом, на котором можно сидеть зрителю, либо быть часть прохода. Всего существует два типа проходов: вертикальный и горизонтальный, оба проходят от края до края. По проходам можно перемещаться свободно, не мешая зрителям. Дополнительно, по периметру зала тоже можно перемещаться свободно.

Вам дано описание зала с указанием проходов и уже занятых мест. Определите минимальное количество человек, которое необходимо потревожить Васе, чтобы добраться до своего места. Помимо прохождения по проходам, Вася может двигаться вдоль любого ряда. Считается, что Вася тревожит зрителя, если он проходит через его место на пути к своему. Аналогичное движение в направлении, перпендикулярном рядам, невозможно. Однако, если номер ряда места Васи на единицу больше координаты горизонтального прохода, то Вася его может занять, не потревожив зрителей. В направлении уменьшения координаты ряда Васи относительно горизонтальных проходов Вася двигаться не может, так как ему мешают спинки кресел.

Рассмотрим пример зрительного зала:

Здесь 9 рядов (H = 9) и 21 место в ряду (W =21). В зале помимо Васи 10 зрителей (обозначены кругами) со следующими координатами: (2,3), (9,7), (5,8), (1,9), (5,13), (1,15), (8,15), (5,17), (5,18), и (5,21). Место Васи обозначено смайликом и находится в координате (5,15). Также здесь три вертикальных прохода в координатах 5, 11, 19 и два горизонтальных прохода в координатах 3 и 7. Васе оптимально двигаться через вертикальный проход 11, потревожив всего одного зрителя (5,13). Вертикальные проходы Вася использовать не может. Но, если бы его ряд был на единицу меньше, то он смог бы через горизонтальный проход 3 занять свое место, не мешая другим зрителям.

Входные данные

В первой строке входного файла INPUT.TXT заданы четыре целых числа W, H, C и P (1 ≤ W, H ≤ 10⁹, 0 ≤ C, P ≤ 10⁵), где W и H — размеры кинозала, C — количество уже занятых мест, P — количество проходов.

В следующих P строках описаны проходы. Горизонтальный проход описывается как «hor h_i» (1 ≤ h_i ≤ H), а вертикальный — «vert v_i» (1 ≤ v_i ≤ W).

Затем в C строках записаны координаты (a_i, b_i) занятых мест (1 ≤ a_i ≤ H, 1 ≤ b _i ≤ W).

Последняя строка содержит координаты места Васи в аналогичном формате. Гарантируется, что ни одно место не указано дважды, а так же то, что места не находятся в проходах.

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число — минимальное количество людей, которое нужно потревожить Васе.

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	10 5 8 2 vert 3 vert 8 2 2 5 6 1 7 3 4 3 6 3 7 4 10 1 4 3 5	1
2	5 5 2 2 hor 3 vert 4 4 1 4 3 4 2	0

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]