Вы играете в компьютерную игру «Шахматы 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
Картинка к примеру, в которой серым выделены клетки, бьющиеся хотя бы одним разведчиком: