Робот стоит в левом нижнем углу
прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вверх или по диагонали вправо вверх. На каждый шаг вправо робот затрачивает 15 единиц энергии, на шаг вверх – 20 единиц, на шаг по диагонали – 10 единиц. В каждой клетке, включая начальную и конечную, робот пополняет запас энергии на величину, равную записанному в этой клетке числу. В начальный момент (до подзарядки в начальной клетке) запас энергии робота равен нулю. Необходимо перевести робота в правый верхний угол поля. Определите максимальное и минимальное значения запаса энергии, который может быть у робота после завершения маршрута и подзарядки в последней клетке. В ответе запишите два числа: сначала максимально возможное значение, затем минимально возможное.
Пример входных данных (для таблицы размером 4×4):
При указанных входных данных максимальное значение 311 получится при движении по маршруту 36 → 97 → 49 → 52 → 83 → 64 → 35, а минимальное значение 83 при движении по маршруту 36 → 7 → 8 → 52 → 25 → 35. В ответе в данном случае надо записать числа 311 и 83.