#P1612F. Armor and Weapons

Armor and Weapons

Description

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

Initially, Monocarp's character has got only the 11-st armor set and the 11-st weapon. Monocarp can obtain a new weapon or a new set of armor in one hour. If he wants to obtain the kk-th armor set or the kk-th weapon, he must possess a combination of an armor set and a weapon that gets his power to kk 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 nn-th armor set and the mm-th weapon. What is the minimum number of hours he has to spend on it?

The first line contains two integers nn and mm (2n,m21052 \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 qq (0qmin(2105,nm)0 \le q \le \min(2 \cdot 10^5, nm)) — the number of combinations that synergize well.

Then qq lines follow, the ii-th line contains two integers aia_i and bib_i (1ain1 \le a_i \le n; 1bim1 \le b_i \le m) meaning that the aia_i-th armor set synergizes well with the bib_i-th weapon. All pairs (ai,bi)(a_i, b_i) are distinct.

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

Input

The first line contains two integers nn and mm (2n,m21052 \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 qq (0qmin(2105,nm)0 \le q \le \min(2 \cdot 10^5, nm)) — the number of combinations that synergize well.

Then qq lines follow, the ii-th line contains two integers aia_i and bib_i (1ain1 \le a_i \le n; 1bim1 \le b_i \le m) meaning that the aia_i-th armor set synergizes well with the bib_i-th weapon. All pairs (ai,bi)(a_i, b_i) are distinct.

Output

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

Samples

样例输入 1

3 4
0

样例输出 1

3

样例输入 2

3 4
2
1 1
1 3

样例输出 2

2

Note

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

  1. Obtain the 22-nd weapon using the 11-st armor set and the 11-st weapon;
  2. Obtain the 33-rd armor set using the 11-st armor set and the 22-nd weapon;
  3. Obtain the 44-th weapon using the 33-rd armor set and the 22-nd weapon.

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

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