Description

“The essence of war between nations is the struggle to seize resources” is the core concept of the entire game, and this mini-game is no exception.

Simply put, the player needs to choose a sub-rectangle on an $R\times C$ rectangular land.

The system randomly generates $N$ resource points; the coordinates of the $i$-th resource point are $(x_i,y_i)$.

The more resource points lie within the player's chosen rectangular land, the greater the reward.

Tragically, although Xiao Lan's friend is exceptionally capable, they also have terrible RP, and the region they choose always contains no resource points.

One day, Xiao Lan's friend finally decided to complain to the game's developer. To collect evidence, they want to count how many regions contain at least one resource point.

Specifically, you need to compute how many four-tuples $(LB,DB,RB,UB)$ satisfy $1\le LB\le RB\le R,1\le DB\le UB\le C$, and there exists an $i$ such that $LB\le x_i\le RB,DB\le y_i\le UB$ are both true.

As Xiao Lan's friend, this is naturally your duty.

Input Format

The first line contains three positive integers $R,C,N$.

Then there are $N$ lines; each line contains two integers $x_i,y_i$, representing the coordinates of the $i$-th resource point.

Output Format

Output a single integer on one line, the number of regions that contain at least one resource point.

5 5 4
1 2
2 3
3 5
4 1

139

Hint

• Constraints:
  • For 20% of the testdata, $N\le 50$.
  • For 40% of the testdata, $N\le 2\times 10^3$.
  • For 100% of the testdata, $1\le R,C\le 4\times 10^4$, $1\le N\le 10^5$; resource point positions are pairwise distinct and are generated randomly.

Translated by ChatGPT 5