CF1612F.Armor and Weapons

Monocarp plays a computer game. There are $n$ different sets of armor and $m$ different weapons in this game. If a character equips the $i$-th set of armor and wields the $j$-th weapon, their power is usually equal to $i + j$; but some combinations of armor and weapons synergize well. Formally, there is a list of $q$ ordered pairs, and if the pair $(i, j)$ belongs to this list, the power of the character equipped with the $i$-th set of armor and wielding the $j$-th weapon is not $i + j$, but $i + j + 1$.

Initially, Monocarp's character has got only the $1$-st armor set and the $1$-st weapon. Monocarp can obtain a new weapon or a new set of armor in one hour. If he wants to obtain the $k$-th armor set or the $k$-th weapon, he must possess a combination of an armor set and a weapon that gets his power to $k$ or greater. Of course, after Monocarp obtains a weapon or an armor set, he can use it to obtain new armor sets or weapons, but he can go with any of the older armor sets and/or weapons as well.

Monocarp wants to obtain the $n$-th armor set and the $m$-th weapon. What is the minimum number of hours he has to spend on it?

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 获得某件武器或某套护甲后，他即可用其进一步获取新的护甲或武器；同时，他仍可继续使用此前已获得的任意护甲和/或武器。

Monocarp 希望获得第 $n$ 套护甲和第 $m$ 把武器。他最少需要花费多少小时？

The first line contains two integers $n$ and $m$ ($2 \le n, m \le 2 \cdot 10^5$) — the number of armor sets and the number of weapons, respectively.

The second line contains one integer $q$ ($0 \le q \le \min(2 \cdot 10^5, nm)$) — the number of combinations that synergize well.

Then $q$ lines follow, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$; $1 \le b_i \le m$) meaning that the $a_i$-th armor set synergizes well with the $b_i$-th weapon. All pairs $(a_i, b_i)$ are distinct.

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

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

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

Print one integer — the minimum number of hours Monocarp has to spend to obtain both the $n$-th armor set and the $m$-th weapon.

输出一个整数——Monocarp 为获得第 $n$ 套护甲和第 $m$ 件武器所需花费的最少小时数。

In the first example, Monocarp can obtain the strongest armor set and the strongest weapon as follows:

1. Obtain the $2$-nd weapon using the $1$-st armor set and the $1$-st weapon;
2. Obtain the $3$-rd armor set using the $1$-st armor set and the $2$-nd weapon;
3. Obtain the $4$-th weapon using the $3$-rd armor set and the $2$-nd weapon.

In the second example, Monocarp can obtain the strongest armor set and the strongest weapon as follows:

1. Obtain the $3$-rd armor set using the $1$-st armor set and the $1$-st weapon (they synergize well, so Monocarp's power is not $2$ but $3$);
2. Obtain the $4$-th weapon using the $3$-rd armor set and the $1$-st weapon.

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

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

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

1. 使用第 $1$ 套护甲和第 $1$ 把武器获得第 $3$ 套护甲（它们协同效果极佳，因此 Monocarp 的力量值不是 $2$，而是 $3$）；
2. 使用第 $3$ 套护甲和第 $1$ 把武器获得第 $4$ 把武器。