D. Шахматный дозор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Не умеешь играть по правилам? Придумай свои!
— Разработчики игр.

Вы играете в компьютерную игру «Шахматы 2023». Как и в обычных шахматах, здесь есть поле, однако, в отличие от них, оно имеет размеры $$$n \times m$$$.

Кроме того, в «Шахматах 2023» есть особая фигура «Разведчик», которая атакует все клетки, которые находятся правее и ниже этой фигуры. На данный момент на поле находятся $$$q$$$ «Разведчиков». Ваша задача заключается в том, чтобы посчитать количество клеток, атакованных «Разведчиками».

Будем считать, что клетка, на которой стоит «разведчик», тоже считается атакованной.

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

В первой строке заданы три целых числа $$$n, \, m, \, q$$$ $$$(1 \le n, \, m \le 10^9, \, 1 \le q \le 10^5)$$$ — размеры поля и количество «Разведчиков» соответственно.

В следующих $$$q$$$ строках описываются положение «Разведчиков».

Положение каждого «Разведчика» описывается двумя числами $$$x, \, y$$$ $$$(1 \le x \le n, \, 1 \le y \le m)$$$ — номер строки (считая сверху) и номер столбца (считая слева), на пересечении которых стоит «Разведчик».

Гарантируется, что никакие два разведчика не стоят в одной клетке.

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

Выведите одно число — количество атакованных клеток.

Система оценки
ГруппаДоп. ограниченияБаллыНеобх. подгруппы
$$$1$$$$$$n, \, m, \, q \le 100$$$$$$20$$$—
$$$2$$$$$$n, \, m \le 1000$$$$$$30$$$$$$1$$$
$$$3$$$$$$n = 1, \, m \le 10^5$$$$$$10$$$—
$$$4$$$$$$n \le 10^5, \, m = 1$$$$$$10$$$—
$$$5$$$—$$$30$$$$$$1, \, 2, \,\ 3,\ 4$$$

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

Пример
Входные данные
8 15 3
3 10
5 7
6 12
Выходные данные
48
Примечание

Картинка к примеру, в которой серым выделены клетки, бьющиеся хотя бы одним разведчиком: