AT_abc008_4 [ABC008D] 金塊ゲーム

高桥君正在玩一个基于无限二维网格的游戏。网格坐标系以 $(0, 0)$ 为原点，向东为 $x$ 轴正方向，向北为 $y$ 轴正方向。坐标为 $(x, y)$ 的格子表示从原点向东移动 $x$ 格（若 $x$ 为负则向西移动 $-x$ 格），向北移动 $y$ 格（若 $y$ 为负则向南移动 $-y$ 格）的位置。 网格中存在 $W \times H$ 个金块，分布在所有满足 $1 \leq p \leq W$ 且 $1 \leq q \leq H$ 的格子 $(p, q)$ 上。其中有恰好 $N$ 个格子设有金块回收装置（编号 $1$ 至 $N$）。装置满足以下条件： - 任意两个装置所在的格子 $(a, b)$ 和 $(c, d)$ 都满足 $a \neq c$ 且 $b \neq d$ - 每个装置所在的格子互不相同 当装置启动时，首先回收所在格子的金块，然后向东南西北四个方向延伸机械臂进行扩展回收。机械臂的延伸需满足以下规则： - **东向**：选择整数 $p > x+1$，使得区间 $(x+1, y)$ 到 $(p-1, y)$ 的格子均有金块，且 $(p, y)$ 无金块。回收该区间所有金块。 - **西向**：选择整数 $p < x-1$，使得区间 $(p+1, y)$ 到 $(x-1, y)$ 的格子均有金块，且 $(p, y)$ 无金块。回收该区间所有金块。 - **南向**：选择整数 $q < y-1$，使得区间 $(x, q+1)$ 到 $(x, y-1)$ 的格子均有金块，且 $(x, q)$ 无金块。回收该区间所有金块。 - **北向**：选择整数 $q > y+1$，使得区间 $(x, y+1)$ 到 $(x, q-1)$ 的格子均有金块，且 $(x, q)$ 无金块。回收该区间所有金块。 对于每个方向，若不存在满足条件的 $p$ 或 $q$，则无法在该方向延伸机械臂。此外，若某个方向存在可回收的金块，则必须执行回收操作。下图展示了满足条件的回收示例（图中以 `M` 表示装置，粗框表示可回收范围）。  高桥君需要决定所有装置的启动顺序，不同的顺序可能导致最终回收数量不同。由于高桥君希望最大化金块回收量，请编写程序计算可能获得的最大金块数量。

输入通过标准输入给出： > $W$ $H$ > $N$ > $X_1$ $Y_1$ > $X_2$ $Y_2$ > ... > $X_N$ $Y_N$ - 第 1 行：两个整数 $W$ ($1 \leq W \leq 10^6$) 和 $H$ ($1 \leq H \leq 10^6$) - 第 2 行：整数 $N$ ($1 \leq N \leq 30$) - 后续 $N$ 行：每行两个整数 $X_i$ ($1 \leq X_i \leq W$) 和 $Y_i$ ($1 \leq Y_i \leq H$)，表示第 $i$ 个装置的位置 保证所有装置的位置满足 $X_i \neq X_j$ 且 $Y_i \neq Y_j$（$i \neq j$）

输出可回收金块的最大数量（末尾换行）

### 部分分 - 数据集 1 ($N \leq 8$, $W,H \leq 80$)：80 分 - 数据集 2 ($W,H \leq 80$)：合计 99 分 - 数据集 3 (无限制)：合计 100 分 ### 样例解释 1 输入样例 1 的初始状态如下图所示（图片链接保留）：  按照 1 号、2 号、3 号装置的顺序启动，可以回收 19 个金块，操作过程如下图所示：  ### 样例解释 2 存在可回收全部金块的启动顺序 翻译由 DeepSeek R1 完成