Задача #6038

Квадрат разлинован на NxN клеток (2 < N < 19). В каждой клетке записано целое положительное число, соответствующее значению в ячейке таблицы в файле 18-1.xls. Исполнитель Робот имеет три команды ВПРАВО, ВВЕРХ и ДИАГОНАЛЬ, которые, соответственно, перемещают его на одну клетку вправо, на одну клетку вверх или на одну клетку вверх и право по диагонали.

Робот двигается только в рамках поля, выход за границы запрещен. Начало движения робота – левая нижняя клетка, конец – верхняя правая клетка. При прохождении клетки к счету Робота прибавляется число, записанное в соответствующей ячейки таблицы.

Какой максимальный и минимальный счет может быть получен в результате работы исполнителя? В ответе запишите два числа – сначала максимально возможный счет Робота, затем минимальный.

Пример входных данных:

В качестве ответа необходимо привести сначала максимальное полученное значение, затем наименьшее.

91 35