Лягушка Лея путешествует по двумерной координатной плоскости. В данный момент она находится в точке \((0,0)\) и хочет добраться до точки \((x,y)\). За один ход она выбирает целое число \(d\) такое, что \(0 \leq d \leq k\) и прыгает на \(d\) позиций вперед в том направлении, в котором она смотрит.
Изначально она смотрит в положительном направлении оси \(x\). После каждого хода она будет чередовать направление взгляда между положительным направлением оси \(x\) и положительным направлением оси \(y\) (то есть, на втором ходу она будет смотреть в положительном направлении оси \(y\), на третьем ходу — в положительном направлении оси \(x\) и так далее).
Какое минимальное количество ходов ей нужно сделать, чтобы приземлиться в точке \((x,y)\)?
Выходные данные
Для каждого набора входных данных выведите количество прыжков, которые необходимо сделать Лее, в отдельной строке.
Примечание
В первом примере один из оптимальных наборов движений — это если Лея прыгает следующим образом: (\(0,0\)) \(\rightarrow\) (\(2,0\)) \(\rightarrow\) (\(2,2\)) \(\rightarrow\) (\(3,2\)) \(\rightarrow\) (\(3,5\)) \(\rightarrow\) (\(6,5\)) \(\rightarrow\) (\(6,8\)) \(\rightarrow\) (\(9,8\)) \(\rightarrow\) (\(9,11\)). Это занимает 8 прыжков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
9 11 3
0 10 8
1000000 100000 10
|
8
4
199999
|