D - Grid game 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 800 点

問題文

高橋君と青木君は H 行 W 列のマス目を使ってゲームをします。 このマス目上には N 個の障害物があり、i 番目の障害物は (X_i,Y_i) にあります。 ただし、i 行 j 列目 (1 \leq i \leq H, 1 \leq j \leq W) にあるマスを (i,j) で表すことにします。 また、どの障害物も (1,1) にはなく、(1,1) には 1 つの駒が置いてあります。

そこで、高橋君と青木君は高橋君から始めて、交互に以下の行動のいずれかを行います。

  • 駒を隣り合うマスに動かす。 ただし、駒の位置を (x,y) としたとき、高橋君は (x+1,y) にのみ、青木君は (x,y+1) にのみ駒を動かすことができる。 また、動かすことのできるマスが存在しない、もしくは、動かす予定のマス目に障害物がある場合はこの行動をとることはできない。
  • 駒を動かさず、マス目を元の状態のまま行動を終える。

2 回連続で駒が動かされなかった場合、そこでゲームを終了します。

高橋君はできるだけ多くの回数の行動 (駒を動かさないのも含む) を行ってゲームを終えたいですが、 青木君はできるだけ少ない回数の行動を行ってゲームを終えたいです。 このとき、高橋君が行うことになる行動の回数は何回か求めてください。

制約

  • 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 は整数

入力

入力は以下の形式で標準入力から与えられる。

H W N
X_1 Y_1
:
X_N Y_N

出力

高橋君が行うことになる行動の回数を出力せよ。

入力例 1

3 3 1
3 2

出力例 1

2

ゲームの一例は以下のようになります。

  • 高橋君が駒を (2,1) に動かす。
  • 青木君が駒を動かさない。
  • 高橋君が駒を (3,1) に動かす。
  • 青木君が駒を動かさない。
  • 高橋君が駒を動かさない。

この場合は高橋君は 3 回の行動を行いますが、 両者が最適に行動すれば 2 回しか高橋君は行動せずにゲームが終了します。

入力例 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

Score : 800 points

Problem Statement

Takahashi and Aoki will play a game using a grid with H rows and W columns of square cells. There are N obstacles on this grid; the i-th obstacle is at (X_i,Y_i). Here, we represent the cell at the i-th row and j-th column (1 \leq i \leq H, 1 \leq j \leq W) by (i,j). There is no obstacle at (1,1), and there is a piece placed there at (1,1).

Starting from Takahashi, he and Aoki alternately perform one of the following actions:

  • Move the piece to an adjacent cell. Here, let the position of the piece be (x,y). Then Takahashi can only move the piece to (x+1,y), and Aoki can only move the piece to (x,y+1). If the destination cell does not exist or it is occupied by an obstacle, this action cannot be taken.
  • Do not move the piece, and end his turn without affecting the grid.

The game ends when the piece does not move twice in a row.

Takahashi would like to perform as many actions (including not moving the piece) as possible before the game ends, while Aoki would like to perform as few actions as possible before the game ends. How many actions will Takahashi end up performing?

Constraints

  • 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 and Y_i are integers.

Input

Input is given from Standard Input in the following format:

H W N
X_1 Y_1
:
X_N Y_N

Output

Print the number of actions Takahashi will end up performing.

Sample Input 1

3 3 1
3 2

Sample Output 1

2

For example, the game proceeds as follows:

  • Takahashi moves the piece to (2,1).
  • Aoki does not move the piece.
  • Takahashi moves the piece to (3,1).
  • Aoki does not move the piece.
  • Takahashi does not move the piece.

Takahashi performs three actions in this case, but if both players play optimally, Takahashi will perform only two actions before the game ends.

Sample Input 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

Sample Output 2

6

Sample Input 3

100000 100000 0

Sample Output 3

100000