题目描述

高桥和青木将使用一个$H$行$W$列的网格，其中每个方格是一个正方形的格子。网格上有$N$个障碍物；第$i$个障碍物位于$(X_i,Y_i)$的位置。在这里，我们用$(i,j)$表示第$i$行第$j$列的格子($1 \leq i \leq H, 1 \leq j \leq W$)。在$(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$
• 若$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)$。
• 青木不移动棋子。
• 高桥不移动棋子。

在这种情况下，高桥执行了三个动作，但如果两位选手都采取最优策略，高桥在游戏结束前只会执行两个动作。

样例输入 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