Исполнитель Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Расход энергии на запуск робота равен числу, записанному в стартовой клетке. В дальнейшем расход энергии на шаг из одной клетки в другую равен абсолютной величине разности чисел, записанных в этих клетках. Определите минимальный и максимальный расход энергии при переходе робота из левой нижней клетки поля в правую верхнюю. В ответе запишите два числа: сначала минимальный расход энергии, затем – максимальный.
Пример входных данных:
При указанных входных данных минимальное значение получится при движении по маршруту 41 → 19 → 17 → 23 → 11 → 8 → 12. Расход энергии на этом пути равен
41 + (41 – 19) + (19 – 17) + (23 – 17) + (23 – 11) + (11 – 8) + (12 – 8) = 90.
Максимальное значение получится при движении по маршруту 41 → 7 → 17 → 26 → 11 → 48 → 12, расход энергии в этом случае равен 182. Ответ: 90 182.
Исходные данные записаны в файле 18-170.xls в виде электронной таблицы, каждая ячейка которой соответствует клетке поля. В ответе укажите два числа — сначала минимальный расход энергии, затем – максимальный.