問題文
高桥正在玩某个游戏。在这个游戏中,游戏是在垂直和水平方向无限延伸的网格上进行的。每个正方形具有正方形形状,每条边平行于东西方向或南北方向。一些正方形有(0,0) 被分配,并且从这个广场向东 x 质量 (x<0 向西 -x 继续向北 y 质量 (y<0 向南 -y ( 分配了一组数字x,y)。
在广场上 有 W × H 金块。这些金块 1 ≦ p ≦ W 和 所有满足 1 ≦ q ≦ H (p,q)到 1 被一一放置。而且,就在有金块的方块之外 N 广场上有一个金块回收装置。该设备有 来自 1 它们的编号最大为 N 。其中 2 一平方 ( 关于a,b) , (c,d),2 如果两个方格中都有设备,a≠c 和 所有满足 b≠d 。此外,多个设备不能位于同一个方块中。起初,金块回收设备都不起作用。
金块回收装置运行时,首先会收集该装置所在方格内的金块。之后,您可以通过向北、南、东、西各个方向延伸起重机来收集更多金块。由于吊车的性质,吊车下降的区域必须没有金块,而需要回收的区域必须有连续的金块。换句话说,有起重机的正方形(x,y),只有在以下条件下才能降低起重机并收集金块。
-
向东方向收集的处理:满足以下条件的整数 选择 p 。之后,x+1 ≦ i ≦ p-1 (i,y) 收集金块。
- 条件:p > x+1 和x+1 ≦ i ≦ p-1 (i,y) 有一个金块,并且有一个正方形 (p,y) 没有金块。
-
向西方向采集的过程:满足以下条件的整数 p 。之后,p+1 ≦ i ≦ x-1 (i,y) 收集金块。
- 条件:p < x-1 和p+1 ≦ i ≦ x-1 (i,y) 有一个金块,并且有一个正方形 (p,y) 没有金块。
-
向南方向采集的过程:满足以下条件的整数 q 。之后,q+1 ≦ j ≦ y-1 (x,j) 收集金块。
- 条件:q < y-1 和q+1 ≦ j ≦ y-1 (x,j) 有一个金块,并且有一个正方形 (x,q) 没有金块。
-
向北方向收集的处理:满足以下条件的整数 q 。之后,y+1 ≦ j ≦ q-1 (x,j) 收集金块。
- 条件:q > y+1 和y+1 ≦ j ≦ q-1 (x,j) 有一个金块,并且有一个正方形 (x,q) 没有金块。
满足每个方向的条件 p 或 如果 q 不存在,则起重机无法沿该方向延伸。
另外,如果可以在各个方向收集金块,那么您一定要收集它们。满足条件的收集方法的示例如下所示。然而,在下图中,该设备是
用符号 M 表示,可恢复范围用粗框表示。

高桥打算按确定的顺序操作所有设备。根据操作顺序的不同,最终获得的金块数量可能会有所不同。热爱金块的高桥先生希望自己最终能获得的金块数量最大化。
我希望你创建一个程序来计算高桥位置的最大值。
入力
输入将以以下格式从标准输入提供。
W H N X_1 Y_1 X_2 Y_2 : X_N Y_N
- 1 行包含有关金块数量和位置的信息。 2 整数 W (1 ≦ W ≦ 10^6) 和 H (1 ≦ H ≦ 10^6) 用空格分隔。
- 2 行包含一个整数,表示金条回收设备的数量。 给出了 N (1 ≦ N ≦ 30) 。 来自行
- 3 从行 N 行数过多 关于第 i (1 ≦ i ≦ N) 第几行包含,i 个设备所在的方格 2 整数 X_i (1 ≦ X_i ≦ W) 和 Y_i (1 ≦ Y_i ≦ H) 用空格分隔。这是i 该设备是平方 (X_i , Y_i)。
此外,该输入还满足以下条件。
- 任何 关于 2 整数 i,j (1 ≦ i < j ≦ N) ,X_i ≠ X_j 和 所有满足 Y_i ≠ Y_j 。
部分点
针对此问题设置了部分分数。
- N ≦ 8 , W ≦ 80 , H ≦ 80 的数据集 如果您正确回答 1 , 给出80 点。 如果您正确回答
- W ≦ 80 , H ≦ 80 的数据集 如果您正确回答 2 ,那么 19 点已给出,总分 获得 99 点。
- 没有附加约束的数据集 3 ,那么 1 点已给出,总分 获得 100 点。
出力
输出可以收集的最大金块数量。还在输出末尾添加换行符。 在
入力例1
6 4 3 2 4 3 1 4 3
出力例1
19
入力例 1 中,初始状态如下。

如下图, 通过按照第1 番目、2 番目、3 个设备的顺序执行, 您可以收集19 金块。

入力例2
3 3 3 1 1 2 3 3 2
出力例2
9
如果你操作得当,你可以收集所有的金块。
入力例3
15 10 8 7 10 12 8 4 4 5 7 9 9 1 6 6 5 3 2
出力例3
112