Counting Resource Rectangles

This problem is based on the idea that "the essence of war in a country is to seize resources", and the same concept applies here.

You are given a rectangular grid of size \(R \times C\). The system randomly places \(N\) resource points on the grid; the \(i\)-th resource point is at coordinates \((x_i, y_i)\). A user selects a subrectangle of the grid defined by the quadruple \((LB, DB, RB, UB)\) with the conditions:

[ 1 \le LB \le RB \le R, \quad 1 \le DB \le UB \le C ]

A subrectangle contains a resource point if there exists an index \(i\) such that:

[ LB \le x_i \le RB \quad \text{and} \quad DB \le y_i \le UB. ]

Your task is to compute the number of subrectangles that contain at least one resource point. Equivalently, if the total number of subrectangles in the \(R \times C\) grid is

[ \text{Total} = \frac{R(R+1)}{2} \times \frac{C(C+1)}{2}, ]

and the number of subrectangles that do not contain any resource point is computed to be \(E\), then your answer is:

[ \text{Answer} = \text{Total} - E. ]

Note: The subrectangle that does not contain any resource point (an empty rectangle) can be counted efficiently using a dynamic programming approach by processing the grid row by row.

inputFormat

The first line contains three integers \(R\), \(C\), and \(N\) (the number of rows, columns, and resource points respectively).

Each of the next \(N\) lines contains two integers \(x_i\) and \(y_i\) representing the coordinates of a resource point. It is guaranteed that \(1 \le x_i \le R\) and \(1 \le y_i \le C\).

outputFormat

Output a single integer: the number of subrectangles of the \(R\times C\) grid that contain at least one resource point.

sample

2 2 1
1 1

4