配点: 100 点
問題文
Gigacord 买了房子。这房子在左边和右边 H 分割,之前和之后 W 分割总计 它分为 H \times W 部分。从左边开始 从前面数第 i th,从前面 j 第一个方格 表示为 (i, j) 。
很快 对象放置在 N 部分中。i 该项目是一个分区 (r_i, c_i) 它占据了整个区域。而且,这些物体不会移动。
Gigacord 在这所房子里有一个壁橱。 1 我决定安装一个。壁橱必须是与房屋外墙平行的矩形,壁橱所在区域不得放置任何物品。不过,地震发生时衣柜移动的话就不好了,所以可以考虑以下摆放方式: 1 我决定选择一个。
- 无论您尝试向哪个方向移动衣柜而不改变其方向,它都会撞到物体或房屋的外墙,并且您将无法移动它。
例如,您可以按如下方式布置衣柜。

但是,不符合条件的衣柜是不能放置的。

找出满足条件的壁橱排列数量。
制約
- 1 \leq H \leq 5 \ 000
- 1 \leq W \leq 5 \ 000
- 0 \leq N \leq 201 \ 900
- 1 \leq r_i \leq H
- 1 \leq c_i \leq W
- N 物品均放置在不同的隔间中
- 输入都是整数
部分点
这个问题被分成了几个子任务,如果你正确回答了该子任务的所有测试用例,那么你就被认为已经正确回答了“这个子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (2 点) H = 1, W = 1
- (11 点) H = 1, W \leq 25
- (11 点) H \leq 25, W \leq 25
- (19 点) N \leq 10
- (16 点) H \leq 100, W \leq 100
- (17 点) H \leq 350, W \leq 350
- (19 点) H \leq 1500, W \leq 1500
- (5 分) 没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
H W N r_1 c_1 r_2 c_2 : : r_N c_N
出力
请输出即使发生地震也不会移动的衣柜布置数量。
注意
由于输入量较大,建议使用高速输入/输出(例如C++的scanf/printf)。