Задача #1806

(В. Лашин) Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Конь может перемещаться по клеткам, выполняя за одно перемещение один из прыжков: вправо на одну клетку, вниз на две, или вправо на две, вниз на одну, или вправо на две, вверх на одну, или вправо на одну, вверх на две. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Конь пройти не может.

Перед каждым запуском Коня в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Конь забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
В «конечных» клетках поля - тех, из которых Конь не может сделать прыжок, сумма считается итоговой. Таких конечных клеток на поле может быть несколько. При разных запусках итоговые накопленные суммы могут различаться.

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