У каждого неудачника в жизни бывают не только чёрные, но и белые полосы.
Марсианин Вась-Вась отмечает в календаре, представляющем собой таблицу m × n, те дни, когда ему ужасно не повезло. Если Вась-Васю не повезло в j-й день i-й недели, то он закрашивает ячейку таблицы (i, j) в чёрный цвет. Все незакрашенные ячейки в таблице имеют белый цвет.
Будем называть отрезками жизни прямоугольники размером 1 × l либо l × 1. Белыми полосами Вась-Вась считает все максимальные по включению белые отрезки таблицы. А сможете ли Вы определить, сколько всего белых полос было в жизни Вась-Вася?
Исходные данные
Первая строка содержит целые числа m, n, k — размеры календаря и количество неудачных дней в жизни Вась-Вася (1 ≤ m, n ≤ 30000; 0 ≤ k ≤ 60000). В следующих k строках перечислены неудачные дни в виде пар (xi, yi), где xi — номер недели,
к которой относится неудачный день, а yi — номер дня в этой неделе (1 ≤ xi ≤ m; 1 ≤ yi ≤ n). Описание каждого неудачного дня встречается только один раз.
Результат
Выведите число белых полос в жизни Вась-Вася.
Примеры
исходные данные | результат |
---|
3 5 4
1 1
1 5
2 2
3 3
| 8
|
5 1 2
2 1
3 1
| 2 |
Автор задачи: Александр Ипатов
Источник задачи: XIII Открытый командный чемпионат УрГУ по программированию