Монокарп играет в компьютерную игру. В этой игре есть \(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\)-е оружие используя \(1\)-й доспех и \(1\)-е оружие;
- Получить \(3\)-й доспех используя \(1\)-й доспех и \(2\)-е оружие;
- Получить \(4\)-е оружие используя \(3\)-й доспех и \(2\)-е оружие.
Во втором примере Монокарп может получить самый сильный доспех и самое сильное оружие следующим образом:
- Получить \(3\)-й доспех используя \(1\)-й доспех и \(1\)-е оружие (они хорошо сочетаются, а значит сила Монокарпа равна не \(2\), а \(3\));
- Получить \(4\)-е оружие используя \(3\)-й доспех и \(1\)-е оружие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
0
|
3
|
|
2
|
3 4
2
1 1
1 3
|
2
|