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?

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.