#P3022. [ZJOI2012]小蓝的好友

[ZJOI2012]小蓝的好友

说明

“国家的战争其本质是抢夺资源的战争”是整款游戏的核心理念,这个小游戏也不例外。

简单来说,用户需要在一块 $R\times C$ 的长方形土地上选出一块子矩形。

而系统随机生成了 $N$ 个资源点,第 $i$ 个资源点的坐标为 $(x_i,y_i)$。

位于用户所选的长方形土地上的资源点越多,给予用户的奖励也越多。

悲剧的是,小蓝的好友虽然拥有着极其优秀的能力,但同时也有着极差的 RP,小蓝的好友所选的区域总是没有一个资源点。

终于有一天,小蓝的好友决定投诉这款游戏的制造厂商,为了搜集证据,小蓝的好友想算出至少包含一个资源点的区域的数量。

具体的说,你需要计算有多少个四元组 $(LB,DB,RB,UB)$ 满足 $1\le LB\le RB\le R,1\le DB\le UB\le C$ ,且存在一个 $i$ 使得 $LB\le xi\le RB,DB\le yi\le UB$ 均成立。

作为小蓝的好友,这自然是你分内之事。

输入格式

第一行三个正整数 $R,C,N$。

接下来有 $N$ 行,每行包含两个整数 $x_i,y_i$,表示第 $i$ 个资源点的坐标。

输出格式

一行一个整数,表示至少包含一个资源点的区域的数量。

样例

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

提示

数据规模与约定

  • 对于 $20\%$ 的数据,$N\le 50$。
  • 对于 $40\%$ 的数据,$N\le 2\times 10^3$。
  • 对于 $100\%$ 的数据,$1\le R,C\le 4\times 10^4$,$1\le N\le 10^5$,题目保证资源点的位置两两不同,且位置为随机生成。