Задание выполняется с использованием прилагаемых файлов.
Робот стоит в левом верхнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку вправо, вниз или по диагонали вправо вниз. На каждый шаг вправо робот затрачивает 15 единиц энергии, на шаг вниз – 20 единиц, на шаг по диагонали – 10 единиц. В каждой клетке, включая начальную и конечную, робот пополняет запас энергии на величину, равную записанному в этой клетке числу. В начальный момент (до подзарядки в начальной клетке) запас энергии робота равен нулю.
Необходимо перевести робота в правый нижний угол поля. Определите максимальное и минимальное значения запаса энергии, который может быть у робота после завершения маршрута и подзарядки в последней клетке.
Исходные данные записаны в электронной таблице.
Пример входных данных (для таблицы размером 4×4):
При указанных входных данных максимальное значение 303 получится при движении по маршруту
43 → 49 → 52 → 83 → 22 → 85 → 74, а минимальное значение 141 при движении по маршруту
43 → 49 → 8 → 22 → 74. В ответе в данном случае надо записать числа 303 и 141.
В ответе запишите два числа (в одной строке, через пробел): сначала максимально возможное значение, затем минимально возможное.