F. Доспехи и оружие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру. В этой игре есть $$$n$$$ различных доспехов и $$$m$$$ различных оружий. Если персонаж снаряжен $$$i$$$-м доспехом и владеет $$$j$$$-м оружием, его сила обычно равна $$$i + j$$$; но некоторые комбинации доспехов и оружия хорошо сочетаются. Формально существует список $$$q$$$ упорядоченных пар, и если пара $$$(i, j)$$$ принадлежит этому списку, сила персонажа, снаряженным $$$i$$$-м доспехом и владеющего $$$j$$$-м оружием, составляет не $$$i + j$$$, а $$$i + j + 1$$$.

Изначально персонаж Монокарпа владеет только $$$1$$$-м доспехом и $$$1$$$-м оружием. Монокарп может получить новое оружие или новый доспех за один час. Если он хочет получить $$$k$$$-й доспех или $$$k$$$-е оружие, он должен обладать комбинацией доспеха и оружия, чья суммарная сила $$$k$$$ или больше. Конечно, после того, как Монокарп получит оружие или доспех, он может использовать его для получения новых доспехов или оружия, но также он может использовать любой из старых доспехов и/или оружия.

Монокарп хочет получить $$$n$$$-й доспех и $$$m$$$-е оружие. Какое минимальное количество часов он должен потратить на это?

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — количество доспехов и количество оружия соответственно.

Вторая строка содержит одно целое число $$$q$$$ ($$$0 \le q \le \min(2 \cdot 10^5, nm)$$$) — количество комбинаций, которые хорошо сочетаются.

Затем следуют $$$q$$$ строк, $$$i$$$-я строка содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i \le n$$$; $$$1 \le b_i \le m$$$), что означает, что $$$a_i$$$-й доспех хорошо сочетается с $$$b_i$$$-м оружием. Все пары $$$(a_i, b_i)$$$ различны.

Выходные данные

Выведите одно целое число — минимальное количество часов, которое Монокарп должен потратить на получение как $$$n$$$-го доспеха, так и $$$m$$$-го оружия.

Примеры
Входные данные
3 4
0
Выходные данные
3
Входные данные
3 4
2
1 1
1 3
Выходные данные
2
Примечание

В первом примере Монокарп может получить самый сильный доспех и самое сильное оружие следующим образом:

  1. Получить $$$2$$$-е оружие используя $$$1$$$-й доспех и $$$1$$$-е оружие;
  2. Получить $$$3$$$-й доспех используя $$$1$$$-й доспех и $$$2$$$-е оружие;
  3. Получить $$$4$$$-е оружие используя $$$3$$$-й доспех и $$$2$$$-е оружие.

Во втором примере Монокарп может получить самый сильный доспех и самое сильное оружие следующим образом:

  1. Получить $$$3$$$-й доспех используя $$$1$$$-й доспех и $$$1$$$-е оружие (они хорошо сочетаются, а значит сила Монокарпа равна не $$$2$$$, а $$$3$$$);
  2. Получить $$$4$$$-е оружие используя $$$3$$$-й доспех и $$$1$$$-е оружие.