eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Монети на дошці

Монети на дошці

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Ви маєте шахову дошку розміру 'N' на 'М'. Рядки дошки пронумеровані від '1' до 'N', а стовпці — від 1 до М. Деякі клітинки дошки містять монети. За одну дію Ви можете обрати дві порожні клітинки дошки (r[1], c[1]) та (r[2], c[2]) такі, що r[1]-r[2] = DR, c[1]-c[2] = DC та поставити по одній монеті у кожну з них. Ви можете повторити таку дію довільну кількість разів.

Вам необхідно знайти максимальну кількість монет, що Ви можете поставити на дошку (без урахування тих, що вже були на дошці).

Вхідні дані

У першому рядку п’ять цілих чисел N, М, К, DR та DC через пробіл. Тут К — кількість клітинок дошки, що початково містять монети. Кожен з наступних К рядків містить два цілих числа r[i] та c[i] через пробіл (номер рядка та стовпця j-тої клітинки відповідно).

Вихідні дані

Максимальна кількість монет.

Обмеження

1 ≤ N,М ≤ 1000000000 (10^9),1 ≤ DR, DC ≤ 1000000000 (10^9),0 ≤ K ≤ 100000 (10^5),1 ≤ r[j] ≤ N,1 ≤ c[j] ≤ М,всі клітинки (r[j], c[j]) попарно різні.

Примітки

У першому прикладі Ви маєте порожню дошку 3 на 3, а DR = DC = 1. У першій дії Ви можете обрати пару клітинок (1, 1) та (2, 2),

у другій дії — (1, 2) та (2, 3),

а у третій — (2, 1) та (3, 2).

Приклад

Вхідні дані #1
3 3 0 1 1
Вихідні дані #1
6
Вхідні дані #2
5 4 2 2 1
3 2
3 3
Вихідні дані #2
10
Джерело Літня школа програмування, Ужгород 2016, День 1, Контест Василя БІлецького