406968: GYM102638 D Distributed Computing

A team contest with a new format is going to be held on BruteForces: all tests are open, and a team may consist of any number of people. The final rating change is, of course, evenly distributed among the team members.

On the very first contest the following non-trivial problem was given:

«A table $$$S$$$ of size $$$m \times n$$$ is given. In the cell $$$S_{i, j}$$$ (where $$$1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n$$$) the sum of all integers from $$$1$$$ to $$$i+j$$$ is written. Find the sum of all numbers in the sub-table with corner cells $$$S_{1, 1}$$$ and $$$S_{a, b}$$$ for the given $$$a, b$$$.»

A total of $$$T$$$ tests were prepared for this problem.

Shortly after reading the problem statement, blue coder Vasya came up with a solution: if only we knew the numbers in all cells, then we could just use the regular Fenwick tree!

It is enough for Vasya to compute the numbers in some of the cells, not necessarily all. In order to do so, he decided to invite some green coders to his team, and ask each of them to calculate the number in a cell $$$S_{i, j}$$$ (one green coder will be assigned to exactly one cell). Since the final rating change is evenly distributed among the team members, Vasya wants to invite as few coders as possible. Thus, he wants to compute the numbers in only those cells that are necessary for answering at least one test (i. e. those cells that lie in at least one sub-table).

What is the minimal number of coders that Vasya has to invite to his team so as to accomplish his goal?

In the first line there are two integers, $$$m$$$ and $$$n$$$, that describe the size of the table.

In the second line there is $$$T$$$, the number of tests.

On each of the following $$$T$$$ lines, there are numbers $$$a, b$$$ — coordinates of one of the corners of the sub-tables.

$$$1 \leqslant m, n \leqslant 5000$$$

$$$1 \leqslant T \leqslant 1000$$$

$$$1 \leqslant a \leqslant m$$$

$$$1 \leqslant b \leqslant n$$$

One integer — the minimal number of green coders that Vasya has to invite to his team.

4 4
3
1 3
2 2
4 1

7

5 5
5
3 2
2 1
4 4
3 5
2 4

19