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

Условие

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

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

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

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

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

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

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

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

...

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

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

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

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

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

Первая строка входного файла содержат три натуральных числа n, m и d — размер огорода (количество строк и столбцов) и время пребывания Павла у бабушки. Далее в d строках через пробел расположено по 2 натуральных числа x_i и y_i, обозначающих количество строк и столбцов, арбузы в которых были политы мальчиком в день номер i. Уточним, что эти данные упорядочены по дням, т.е. сначала идёт пара чисел x₁, y₁, затем x₂, y₂ и так далее. Отметим отдельно, что бабушка пронумеровала все строки и столбцы в огороде, и Павел всегда поливает именно x_i первых строк и y_i первых столбцов.

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

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

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

Ограничения

1 ≤ x_i ≤ n ≤ 10⁹

1 ≤ y_i ≤ m ≤ 10⁹

1 ≤ d ≤ 10⁵

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

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

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

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

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

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

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

4 5 3
2 3
1 4
4 1

11