A14710. 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?

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.

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.

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.