分数: 800 点
问题陈述
高桥和青木将玩一个使用网格的游戏 H 行和 W 方形单元格列。 有 N 该网格上有障碍物;的 i- 第一个障碍位于 (X_i,Y_i)。 在这里,我们代表单元格 i第行和 j第列 (1 \leq i \leq H, 1 \leq j \leq W) by (i,j)。 处没有障碍物 (1,1),并且有一块放置在那里 (1,1).
从高桥开始,他和青木交替执行以下动作之一:
- 将棋子移动到相邻的单元格。 这里,设该块的位置为 (x,y)。那么高桥只能将棋子移动到 (x+1,y),青木只能将棋子移动到 (x,y+1)。 如果目标单元格不存在或者被障碍物占据,则无法执行此操作。
- 不要移动棋子,并在不影响网格的情况下结束他的回合。
当棋子连续两次没有移动时游戏结束。
高桥希望在游戏结束前执行尽可能多的动作(包括不移动棋子),而青木希望在游戏结束前执行尽可能少的动作。 高桥最终会表演多少个动作?
约束
- 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
- If i \neq j, (X_i,Y_i) \neq (X_j,Y_j)
- (X_i,Y_i) \neq (1,1)
- X_i 和 Y_i 是整数。
输入
输入由标准输入按以下格式给出:
H W N X_1 Y_1 : X_N Y_N
输出
打印 Takahashi 最终将执行的操作数。
示例输入 1
3 3 1 3 2
示例输出 1
2
例如,游戏进行如下:
- 高桥将棋子移至 (2,1)。
- 青木没有移动棋子。
- 高桥将棋子移至 (3,1)。
- 青木没有移动棋子。
- 高桥没有移动棋子。
在这种情况下,高桥执行了三个动作,但如果两个玩家都发挥最佳,那么高桥在游戏结束前将只执行两个动作。
示例输入 2
10 10 14 4 3 2 2 7 3 9 10 7 7 8 1 10 10 5 4 3 4 2 8 6 4 4 4 5 8 9 2
示例输出 2
6
示例输入 3
100000 100000 0
示例输出 3
100000