Задача 77. Бахча

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Змеи щурят глаза на песке перегретом,

Тополя опадают. Но в травах густых

Тяжело поднимаются жарким рассветом

Перезревшие солнца обветренных тыкв.

В них накопленной силы таится обуза —

Плодородьем добротным покой нагружён,

И изранено спелое сердце арбуза

Беспощадным и острым казацким ножом.

...

Павел Васильев, "Бахча под Семипалатинском", 1929 г.

На лето родители отправили Павла к бабушке помогать ей выращивать на бахче арбузы. Чтобы они выросли большими и вкусными, требуется поливать растения каждый день (на рассвете!), что и было поручено мальчику. Если арбуз был полит, он вырастает на один килограмм (а если не был, то остаётся прежнего размера) за каждый день.

Сам огород представляет собой прямоугольную сетку из n строк и m столбцов, в каждой ячейке которой растёт арбуз, изначально имеющий массу 0 килограмм. Павел привык к богемному образу жизни и очень не любит работать, поэтому в i-й день из всех d, что он будет гостить у бабушки, планирует поливать только арбузы, лежащие на пересечении первых xi строк и первых yi столбцов.

Определите количество арбузов, масса которых останется равной 0.

Формат входных данных

Первая строка входного файла содержат три натуральных числа n, m и d — размер огорода (количество строк и столбцов) и время пребывания Павла у бабушки. Далее в d строках через пробел расположено по 2 натуральных числа xi и yi, обозначающих количество строк и столбцов, арбузы в которых были политы мальчиком в день номер i. Уточним, что эти данные упорядочены по дням, т.е. сначала идёт пара чисел x1, y1, затем x2, y2 и так далее. Отметим отдельно, что бабушка пронумеровала все строки и столбцы в огороде, и Павел всегда поливает именно xi первых строк и yi первых столбцов.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ xi ≤ n ≤ 109

1 ≤ yi ≤ m ≤ 109

1 ≤ d ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, правильно работающие, когда произведение чисел n, m и d не превосходит 106, будут оцениваться в 50 баллов.

Пояснение к примеру

Размер огорода 4 × 5, Павел проведёт у бабушки 3 дня. Смотри рисунок.

Хотя бы один раз политы 9 арбузов. Не политыми ни разу останутся 11 арбузов.

Примеры тестов

Стандартный вход Стандартный выход
1
4 5 3
2 3
1 4
4 1
11

0.085s 0.015s 17