← 返回题目列表

AtCoder · agc029_d

D. 网格游戏

中文机器翻译题面 查看原题

分数: 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