Пам'ятаєте першу задачу? Ця задача дуже схожа.
Дано шахівниця розміром n×m. Тобто з n рядками та m стовпчиками.
У цій шахівниці є фігура — тура. Вона знаходиться у нижньому лівому куті, яка має координати (1,1). Протилежний кут має координати (n,m). Також дано k інших фігур. i-та фігура має координати (xi,yj), де 1≤xi≤n, 1≤yi≤m.
Порахуйте кількість клітин, на які може переміститися тура не більше, ніж за два ходи. Зверніть увагу, що позицію, на які зараз тура, рахувати непотрібно. Тура не може бити інші фігури, а також не може перескакувати через них. Інші фігури не рухаються.
Перший рядок містить три цілі числа n, m, k (1≤n,m≤2⋅105, 0≤k≤2⋅105).
Кожен з наступних k рядків містить два цілі числа xi та yi (1≤xi≤n, 1≤yi≤m). Гарантується, що всі фігури, включно з турою, знаходяться на різних позиціях.
Виведіть одне ціле число.
У першому прикладі можна потрапити у клітини [(1,2),(1,3),(2,1),(2,2),(3,1)].
У другому прикладі можна потрапити в усі клітини.
У третьому прикладі не можна потрапити у жодну клітину.
Четвертий приклад пояснений нижче. Тут T — тура. X — фігура. 1 — позиція, яку можна досягти. 0 — позиція, яку неможливо досягти.
У 60% тестів виконуються обмеження n,m≤1000.
У 80% тестів виконуються обмеження n,m≤10000.