题目描述

高桥君和青木君使用一个 $H$ 行 $W$ 列的格子进行游戏。在这个格子上有 $N$ 个障碍物，第 $i$ 个障碍物位于 $(X_i, Y_i)$。这里，将第 $i$ 行第 $j$ 列的格子表示为 $(i, j)$。此外，任意障碍物都不会在 $(1,1)$，并且 $(1,1)$ 上放有一个棋子。

游戏由高桥君先手，二人轮流进行以下两种操作之一：

• 将棋子移动到相邻的格子。假设棋子当前在 $(x, y)$，高桥君只能将棋子移动到 $(x+1, y)$，青木君只能将棋子移动到 $(x, y+1)$。如果没有可以移动的格子，或者目标格子上有障碍物，则不能进行此操作。
• 不移动棋子，直接结束本回合，保持格子状态不变。

如果连续两回合都没有移动棋子，游戏立即结束。

高桥君希望让游戏持续尽可能多的回合（包括选择不移动棋子的回合），而青木君则希望让游戏尽快结束。请你求出在双方都采取最优策略的情况下，高桥君能够进行的回合数。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出高桥君能够进行的回合数。

样例 1

输入

3 3 1
3 2

输出

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

样例 3

输入

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$ 均为整数

样例解释 1

游戏的一种可能过程如下：

• 高桥君将棋子移动到 $(2,1)$。
• 青木君选择不移动棋子。
• 高桥君将棋子移动到 $(3,1)$。
• 青木君选择不移动棋子。
• 高桥君选择不移动棋子。

在这种情况下，高桥君进行了 $3$ 次操作，但如果双方都采取最优策略，高桥君最多只能进行 $2$ 次操作，游戏就会结束。

由 ChatGPT 4.1 翻译