Задача #2800

(Л. Шастин) Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. В начальный момент Робот обладает запасом энергии, которая расходуется на движение по клеткам. Изначальный запас энергии Робота равен числу, записанному в стартовой клетке. Кроме обычных клеток также есть «заправочные станции» – это клетки, выделенные зелёным цветом. При посещении обычных клеток запас энергии Робота уменьшается на число, записанное в этих клетках; при посещении «заправочных станций» – увеличивается на записанное в них значение.

Определите максимальный и минимальный запас энергии, который может быть у Робота после перехода из левой верхней клетки в правую нижнюю клетку поля. В ответе укажите два числа - сначала максимальное значение, затем минимальное. Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.