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