Тура, але уже складніша
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Пам'ятаєте першу задачу? Ця задача дуже схожа.

Дано шахівниця розміром $$$n \times m$$$. Тобто з $$$n$$$ рядками та $$$m$$$ стовпчиками.

У цій шахівниці є фігура — тура. Вона знаходиться у нижньому лівому куті, яка має координати $$$(1, 1)$$$. Протилежний кут має координати $$$(n, m)$$$. Також дано $$$k$$$ інших фігур. $$$i$$$-та фігура має координати $$$(x_i, y_j)$$$, де $$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$.

Порахуйте кількість клітин, на які може переміститися тура не більше, ніж за два ходи. Зверніть увагу, що позицію, на які зараз тура, рахувати непотрібно. Тура не може бити інші фігури, а також не може перескакувати через них. Інші фігури не рухаються.

Вхідні дані

Перший рядок містить три цілі числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 2 \cdot 10^5$$$).

Кожен з наступних $$$k$$$ рядків містить два цілі числа $$$x_i$$$ та $$$y_i$$$ ($$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$). Гарантується, що всі фігури, включно з турою, знаходяться на різних позиціях.

Вихідні дані

Виведіть одне ціле число.

Система оцінки

У $$$60\%$$$ тестів виконуються обмеження $$$n, m \leq 1\,000$$$.

У $$$80\%$$$ тестів виконуються обмеження $$$n, m \leq 10\,000$$$.

Приклади

Вхідні дані
3 3 2
2 3
3 2
Вихідні дані
5
Вхідні дані
3 3 0
Вихідні дані
8
Вхідні дані
4 4 2
1 2
2 1
Вихідні дані
0
Вхідні дані
4 5 2
3 1
2 4
Вихідні дані
14

Пояснення

У першому прикладі можна потрапити у клітини $$$[(1, 2), (1, 3), (2, 1), (2, 2), (3, 1)]$$$.

У другому прикладі можна потрапити в усі клітини.

У третьому прикладі не можна потрапити у жодну клітину.

Четвертий приклад пояснений нижче. Тут $$$T$$$ — тура. $$$X$$$ — фігура. $$$1$$$ — позиція, яку можна досягти. $$$0$$$ — позиція, яку неможливо досягти.

$$$$$$ \begin{matrix} 0 & 1 & 1 & 0 & 1 \\ X & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & X & 1 \\ T & 1 & 1 & 1 & 1 \\ \end{matrix} $$$$$$