Armor and Weapons

2000ms

524288K

Description:

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?

Input:

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.

Output:

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.

Sample Input:

3 4
0

Sample Output:

Sample Input:

Sample Output:

Note:

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

Obtain the $$$2$$$-nd weapon using the $$$1$$$-st armor set and the $$$1$$$-st weapon;
Obtain the $$$3$$$-rd armor set using the $$$1$$$-st armor set and the $$$2$$$-nd weapon;
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:

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$$$);
Obtain the $$$4$$$-th weapon using the $$$3$$$-rd armor set and the $$$1$$$-st weapon.

Informação

Provedor Codeforces

Código CF1612F