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