eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Защита королевства

Защита королевства

Теодор реализует новую стратегию игры "Оборона Царства". На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В некоторых клетках игрок строит арбалетные башни. Башня защищает все клетки в той же строке и том же столбце. Никакие две башни не находятся на одной строке или столбце.

Штрафом положения является количество клеток в крупнейшем незащищенном прямоугольнике. Например, положение, показанное на рисунке имеет штраф 12.

prb2261

Помогите Теодору написать программу, вычисляющую штраф в заданной позиции.

Входные данные

Первая строка содержит три целых числа: w - ширина сетки, h - высота сетки и n - количество арбалетных башен (1w, h40000; 0nmin(w, h)).

Каждая из следующих n строк содержит два целых числа xi и yi - координаты клетки с башней (1xiw; 1yih).

Выходные данные

Вывести одно число - количество клеток в наибольшем прямоугольнике, не защищенном башнями.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
15 8 3
3 8
11 2
8 6
Выходные данные #1
12
Автор Georgiy Korneev
Источник 2010 ACM NEERC, Northern Subregion, Санкт-Петербург, Октябрь 30, Задача D