Тура, але уже складніша#68

Тура, але уже складніша

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

Дано шахівниця розміром 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

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Приклад 4

Loading
Loading

Примітка

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

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

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

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

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

Оцінювання

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

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