Armor and Weapons

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

Monocarp 正在玩一款电脑游戏。在这款游戏中，有 $n$ 套不同的护甲和 $m$ 种不同的武器。如果角色装备第 $i$ 套护甲并持有第 $j$ 把武器，通常情况下他的战斗力等于 $i + j$；但某些护甲与武器的组合会产生良好的协同效果。具体来说，存在一个包含 $q$ 个有序对的列表，如果组合 $(i, j)$ 在该列表中，则角色装备第 $i$ 套护甲并持有第 $j$ 把武器时的战斗力不是 $i + j$，而是 $i + j + 1$。

最初，Monocarp 的角色只拥有第 $1$ 套护甲和第 $1$ 把武器。Monocarp 每花费一小时可以获得一套新的护甲或一把新的武器。如果他想获得第 $k$ 套护甲或第 $k$ 把武器，他必须拥有一套护甲和一把武器的组合，使得他的战斗力达到 $k$ 或更高。当然，在获得新的护甲或武器后，他可以用它们来获得新的护甲或武器，也可以继续使用之前获得的护甲或武器。

Monocarp 想要获得第 $n$ 套护甲和第 $m$ 把武器。请问他至少需要花费多少小时才能做到？

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$），分别表示护甲的数量和武器的数量。

第二行包含一个整数 $q$（$0 \le q \le \min(2 \cdot 10^5, nm)$），表示具有良好协同效果的组合数量。

接下来的 $q$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le n$，$1 \le b_i \le m$），表示第 $a_i$ 套护甲与第 $b_i$ 把武器协同效果良好。所有 $(a_i, b_i)$ 均互不相同。

输出格式

输出一个整数，表示 Monocarp 至少需要花费多少小时才能获得第 $n$ 套护甲和第 $m$ 把武器。

样例输入 1

3 4
0

样例输出 1

3

样例输入 2

3 4
2
1 1
1 3

样例输出 2

2

提示

在第一个样例中，Monocarp 可以按如下方式获得最强的护甲和武器：

1. 使用第 $1$ 套护甲和第 $1$ 把武器获得第 $2$ 把武器；
2. 使用第 $1$ 套护甲和第 $2$ 把武器获得第 $3$ 套护甲；
3. 使用第 $3$ 套护甲和第 $2$ 把武器获得第 $4$ 把武器。

在第二个样例中，Monocarp 可以按如下方式获得最强的护甲和武器：

1. 使用第 $1$ 套护甲和第 $1$ 把武器获得第 $3$ 套护甲（它们协同效果良好，所以战斗力不是 $2$，而是 $3$）；
2. 使用第 $3$ 套护甲和第 $1$ 把武器获得第 $4$ 把武器。

数据范围

$2\le n,m\le2\cdot10^5$，$0\le q\le\min(2\cdot10^5,nm)$。所有协同组合互不相同。