Бабушкин огород

Антон помогает бабушке поливать огород, который представляет собой прямоугольник из n строк, пронумерованных сверху вниз, и m столбцов, пронумерованных слева направо. Антон q раз поливает некоторые клетки данного огорода следующим образом: он выбирает ячейку с координатами (x, y) (то есть строку номер x и столбец номер y), а затем поливает все клетки ниже и/или правее. Более формально, он поливает все ячейки с координатами (i, j), где i ≥ x и j ≥ y.

Сколько после всех таких операций окажется клеток, которые не были политы ни разу?

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

В первых трёх строках входного файла INPUT.TXT записаны целые числа n, m и q (1 ≤ n, m ≤ 10⁶, 1 ≤ q ≤ 10⁵) – размеры огорода и количество описанных операций.

Следующие 2q строк содержат целые числа x_i, y_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m) – координаты ячейки, которую выбирает Антон в очередной операции.

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

В выходной файл OUTPUT.TXT выведите одно целое число – количество неполитых клеток огорода.

Пример

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

На картинках изображён ход действий Антона в примере из условия.

Исходный огород (3 × 4)	После 1-й операции (x = 2, y = 3)	После 2-й операции (x = 3, y = 2)
1 2 3 4 1 2 3	1 2 3 4 1 2 3	1 2 3 4 1 2 3

	Не полита
	Полита

Операции полива:
1. (2, 3) – полить все клетки с i ≥ 2 и j ≥ 3
2. (3, 2) – полить все клетки с i ≥ 3 и j ≥ 2

Система оценки

Решения, верно работающие при n = 1, получат не менее 10 баллов.

Решения, верно работающие при n ≤ 2, получат не менее 20 баллов.

Решения, верно работающие при n, m ≤ 1000, получат не менее 50 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]