Монети на дошці#7803
Вам дано шахову дошку розміром N \times M. Рядки пронумеровані від до , а стовпці — від до . Деякі клітинки містять монети. За одну операцію можна вибрати дві порожні клітинки (r_1, c_1) і (r_2, c_2) такі, що r_1 - r_2 = DR, c_1 - c_2 = DC, та поставити по одній монеті в кожну з них. Таку операцію дозволено виконувати будь-яку кількість разів.
Потрібно знайти максимальну кількість монет, які можна додатково розмістити на дошці (без урахування початкових монет).
У першому рядку міститься п'ять цілих чисел , , , та . Тут — кількість клітинок, що спочатку містять монети. Кожен з наступних рядків містить по два цілих числа r_i та c_i (номер рядка та стовпця відповідної клітинки).
Виведіть максимальну кількість монет.
Обмеження:
1 \le N, M \le 10^9
1 \le DR, DC \le 10^9
0 \le K \le 10^5
1 \le r_j \le N
1 \le c_j \le M
Усі клітинки (r_j, c_j) попарно різні.
Приклад 1
Приклад 2
У першому прикладі дошка розміром 3 \times 3 порожня, DR = DC = 1. У першій операції можна вибрати пару клітинок та , у другій — та , у третій — та .