ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Белые полосы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
У каждого неудачника в жизни бывают не только чёрные, но и белые полосы. Марсианин Вась-Вась отмечает в календаре, представляющем собой таблицу 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 ≤ xim; 1 ≤ yin). Описание каждого неудачного дня встречается только один раз.

Результат

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

Примеры

исходные данныерезультат
3 5 4
1 1
1 5
2 2
3 3
8
5 1 2
2 1
3 1
2
Автор задачи: Александр Ипатов
Источник задачи: XIII Открытый командный чемпионат УрГУ по программированию
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1628. Белые полосы