Background

At last we have reached the final problem of this selection contest; you are probably already tired of the stories of Xiao Lan and Xiao Bai.

To thank all contestants, the protagonist of this problem is the key figure throughout this contest—Xiao Lan's friend.

After helping Xiao Lan determine the travel route, Xiao Lan's friend is not going to waste this rare summer vacation either.

Unlike Xiao Lan, Xiao Lan's friend does not want to spend time traveling, but instead has set their sights on the newly released real-time strategy game—SangoCraft.

However, on the road to beating the game, a mini-game blocked Xiao Lan's friend's way.

Problem 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