Робот стоит в левом верхнем углу поля, состоящего из \(n\) строк и \(m\) столбцов, в клетке \((1, 1)\).
За один шаг он может перейти в клетку, соседнюю по стороне с текущей:
- \((x, y) \rightarrow (x, y + 1)\);
- \((x, y) \rightarrow (x + 1, y)\);
- \((x, y) \rightarrow (x, y - 1)\);
- \((x, y) \rightarrow (x - 1, y)\).
Робот не может выйти за пределы поля.
В клетке \((s_x, s_y)\) находится смертоносный лазер. Если робот встает в клетку на расстоянии меньше или равном \(d\) к лазеру, то его испепеляет. Расстояния между двумя клетками \((x_1, y_1)\) и \((x_2, y_2)\) равно \(|x_1 - x_2| + |y_1 - y_2|\).
Выведите наименьшее количество шагов, которые может сделать робот, чтобы дойти до клетки \((n, m)\), не испепелившись и не выходя за пределы поля. Если невозможно достичь клетки \((n, m)\), то выведите -1.
Лазер не находится ни в начальной, ни в конечной клетке. Начальная клетка всегда находится на расстоянии больше \(d\) от лазера.
Выходные данные
На каждый набор входных данных выведите одно целое число. Если возможно достичь \((n, m)\) из \((1, 1)\), не испепелившись и не выходя за пределы поля, то выведите наименьшее количество шагов, которые может сделать робот, чтобы ее достичь. Иначе выведите -1.