Пам'ятаєте першу задачу? Ця задача дуже схожа.
Дано шахівниця розміром n \times m. Тобто з рядками та стовпчиками.
У цій шахівниці є фігура — тура. Вона знаходиться у нижньому лівому куті, яка має координати . Протилежний кут має координати . Також дано інших фігур. -та фігура має координати (x_i, y_j), де 1 \leq x_i \leq n, 1 \leq y_i \leq m.
Порахуйте кількість клітин, на які може переміститися тура не більше, ніж за два ходи. Зверніть увагу, що позицію, на які зараз тура, рахувати непотрібно. Тура не може бити інші фігури, а також не може перескакувати через них. Інші фігури не рухаються.
Перший рядок містить три цілі числа , , (1 \leq n, m \leq 2 \cdot 10^5, 0 \leq k \leq 2 \cdot 10^5).
Кожен з наступних рядків містить два цілі числа x_i та y_i (1 \leq x_i \leq n, 1 \leq y_i \leq m). Гарантується, що всі фігури, включно з турою, знаходяться на різних позиціях.
Виведіть одне ціле число.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
У першому прикладі можна потрапити у клітини [(1, 2), (1, 3), (2, 1), (2, 2), (3, 1)].
У другому прикладі можна потрапити в усі клітини.
У третьому прикладі не можна потрапити у жодну клітину.
Четвертий приклад пояснений нижче. Тут — тура. — фігура. — позиція, яку можна досягти. — позиція, яку неможливо досягти.
У тестів виконуються обмеження n, m \leq 1\,000.
У тестів виконуються обмеження n, m \leq 10\,000.