题目描述

高橋君と青木君は $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$ 回連続で駒が動かされなかった場合、そこでゲームを終了します。

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

输入格式

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

$H$ $W$ $N$ $X_1$ $Y_1$ $:$ $X_N$ $Y_N$

输出格式

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

题目大意

高木和青木正在玩一个游戏。
具体地说，他们有一个 $H\times W$ 的矩阵，上面有 $N$ 个障碍物。
在起点 $(1,1)$ 处有一颗小石子，高木先手，和青木将轮流进行以下操作：

• 假设当前石子所在的位置为 $(x,y)$ ，那么如果是轮到高木，他可以选择将石子移动到 $(x+1,y)$ 或者不移动。青木可以将石子移动到 $(x,y+1)$或者不移动。

• 石子移动到的地方不能是障碍物或者矩阵外面。

当一轮操作中高木和青木都没有移动石子时，游戏结束。
现在，高木想尽可能地让游戏轮数变多，而青木则会尽可能地让游戏轮数变少。
请问在双方都采取最优策略地情况下，会进行几轮游戏（最后一轮无法操作也算做一次）。

3 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

6

100000 100000 0

100000

提示

制約

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

Sample Explanation 1

ゲームの一例は以下のようになります。 - 高橋君が駒を (2,1) に動かす。 - 青木君が駒を動かさない。 - 高橋君が駒を (3,1) に動かす。 - 青木君が駒を動かさない。 - 高橋君が駒を動かさない。 この場合は高橋君は $3$ 回の行動を行いますが、 両者が最適に行動すれば $2$ 回しか高橋君は行動せずにゲームが終了します。