分数 : $800$ 分

问题陈述

Takahashi 和 Aoki 将在一个 $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)$ 处放置了一颗棋子。

游戏从 Takahashi 开始，他和 Aoki 交替执行以下动作之一：

• 将棋子移动到相邻的单元格。 这里，设棋子的位置为 $(x,y)$。那么 Takahashi 只能将棋子移动到 $(x+1,y)$，而 Aoki 只能将棋子移动到 $(x,y+1)$。 如果目标单元格不存在或被障碍物占据，则无法执行此操作。
• 不移动棋子，结束他的回合，而不影响网格。

当棋子连续两次不移动时，游戏结束。

Takahashi 希望在游戏结束前尽可能多地执行动作（包括不移动棋子），而 Aoki 希望在游戏结束前尽可能少地执行动作。 Takahashi 最终将执行多少个动作？

约束条件

• $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$

输出

打印 Takahashi 最终将执行的动作数量。

3 3 1
3 2

2

例如，游戏进行如下：

• Takahashi 将棋子移动到 (2,1)。
• Aoki 不移动棋子。
• Takahashi 将棋子移动到 (3,1)。
• Aoki 不移动棋子。
• Takahashi 不移动棋子。

在这种情况下，Takahashi 执行了三次动作，但如果两位玩家都采取最佳策略，Takahashi 最终将仅执行两次动作。

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