Квадрат разлинован на N×N клеток (1 < N < 20). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трёх команд:
вправо,
вверх или
вправо-вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю, а по команде вправо-вверх – на одну клетку вправо и вверх по диагонали. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата записана величина вознаграждения от 1 до 100. Попав в клетку после хода вправо или вверх, Робот получает указанное в ней вознаграждение, а если он попал в клетку после выполнения команды вправо-вверх, вознаграждение удваивается. Это также относится к начальной и конечной клетке маршрута Робота. Определите максимальное и минимальное вознаграждение, которое может получить Робот, пройдя из левой нижней клетки в правую верхнюю. В ответе укажите два числа – сначала максимальное вознаграждение, затем минимальное.
Исходные данные для Робота записаны в файле
18-95.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке квадрата.