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.


-----Examples-----

Input
3 4
0
Output
3
Input
3 4
2
1 1
1 3
Output
2


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

Difficulty: VERY_HARD
Tags: Greedy algorithms

Dynamic programming

Complete search

Shortest paths
Skill types: Dynamic programming

Complete search

Greedy algorithms

Starter code:

Solutions:
def solution():
	(n, m) = map(int, input().strip().split())
	q = int(input())
	a_b = set()
	for _ in range(q):
		(a, b) = map(int, input().strip().split())
		a_b.add((a, b) if n < m else (b, a))
	if n > m:
		(n, m) = (m, n)
	dp = [-1] * (n + 1)
	dp[1] = 1
	result = 0
	while dp[n] != m:
		new_dp = dp[:]
		for i in range(1, n + 1):
			if dp[i] == -1:
				continue
			x = i + dp[i] + ((i, dp[i]) in a_b)
			new_dp[i] = max(new_dp[i], min(x, m))
			new_dp[min(x, n)] = max(new_dp[min(x, n)], dp[i])
		dp = new_dp
		result += 1
	return result
print(solution())


(n, m) = map(int, input().strip().split())
bonus = set()
x = int(input())
for _ in range(x):
	(a, b) = map(int, input().strip().split())
	bonus.add((a, b) if n < m else (b, a))
if n > m:
	(n, m) = (m, n)
weapon_on_armor = [-1] * (n + 1)
weapon_on_armor[1] = 1
answer = 0
while weapon_on_armor[n] != m:
	weapon_on_armor_potential = weapon_on_armor.copy()
	for armor in range(1, n + 1):
		if weapon_on_armor[armor] == -1:
			continue
		current_power = armor + weapon_on_armor[armor] + ((armor, weapon_on_armor[armor]) in bonus)
		new_weapon = min(current_power, m)
		new_armor = min(current_power, n)
		weapon_on_armor_potential[armor] = max(weapon_on_armor_potential[armor], new_weapon)
		weapon_on_armor_potential[new_armor] = max(weapon_on_armor_potential[new_armor], weapon_on_armor[armor])
	answer += 1
	weapon_on_armor = weapon_on_armor_potential
print(answer)