AT_agc029_d [AGC029D] Grid game

高桥君和青木君使用一个 $H$ 行 $W$ 列的格子进行游戏。在这个格子上有 $N$ 个障碍物，第 $i$ 个障碍物位于 $(X_i, Y_i)$。这里，将第 $i$ 行第 $j$ 列的格子表示为 $(i, j)$。此外，任意障碍物都不会在 $(1,1)$，并且 $(1,1)$ 上放有一个棋子。 游戏由高桥君先手，二人轮流进行以下两种操作之一： - 将棋子移动到相邻的格子。假设棋子当前在 $(x, y)$，高桥君只能将棋子移动到 $(x+1, y)$，青木君只能将棋子移动到 $(x, y+1)$。如果没有可以移动的格子，或者目标格子上有障碍物，则不能进行此操作。 - 不移动棋子，直接结束本回合，保持格子状态不变。 如果连续两回合都没有移动棋子，游戏立即结束。 高桥君希望让游戏持续尽可能多的回合（包括选择不移动棋子的回合），而青木君则希望让游戏尽快结束。请你求出在双方都采取最优策略的情况下，高桥君能够进行的回合数。

输入通过标准输入给出，格式如下： > $H$ $W$ $N$ $X_1$ $Y_1$ $:$ $X_N$ $Y_N$

输出高桥君能够进行的回合数。

## 限制条件 - $1 \leq H, W \leq 2 \times 10^5$ - $0 \leq N \leq 2 \times 10^5$ - $1 \leq X_i \leq H$ - $1 \leq Y_i \leq W$ - 当 $i \neq j$ 时，$(X_i, Y_i) \neq (X_j, Y_j)$ - $(X_i, Y_i) \neq (1, 1)$ - $X_i, Y_i$ 均为整数 ## 样例解释 1 游戏的一种可能过程如下： - 高桥君将棋子移动到 $(2,1)$。 - 青木君选择不移动棋子。 - 高桥君将棋子移动到 $(3,1)$。 - 青木君选择不移动棋子。 - 高桥君选择不移动棋子。 在这种情况下，高桥君进行了 $3$ 次操作，但如果双方都采取最优策略，高桥君最多只能进行 $2$ 次操作，游戏就会结束。 由 ChatGPT 4.1 翻译