task_14_1628

Задача 14 (1628. Белые полосы)

Условие

У каждого неудачника в жизни бывают не только чёрные, но и белые полосы. Марсианин Вась-Вась отмечает в календаре, представляющем собой таблицу m × n, те дни, когда ему ужасно не повезло. Если Вась-Васю не повезло в j-й день i-й недели, то он закрашивает ячейку таблицы (i, j) в чёрный цвет. Все незакрашенные ячейки в таблице имеют белый цвет. Будем называть отрезками жизни прямоугольники размером 1 × l либо l × 1. Белыми полосами Вась-Вась считает все максимальные по включению белые отрезки таблицы. А сможете ли Вы определить, сколько всего белых полос было в жизни Вась-Вася?

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Исходные данные

ВПервая строка содержит целые числа m, n, k — размеры календаря и количество неудачных дней в жизни Вась-Вася (1 ≤ m, n ≤ 30000; 0 ≤ k ≤ 60000). В следующих k строках перечислены неудачные дни в виде пар (x_i, y_i), где x_i — номер недели, к которой относится неудачный день, а _i — номер дня в этой неделе (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ n). Описание каждого неудачного дня встречается только один раз.

Результат

Выведите число белых полос в жизни Вась-Вася.

Примеры

Исходные данные	Результат
3 5 4 1 1 1 5 2 2 3 3	8
5 1 2 2 1 3 1	2