Динамическое программирование в электронных таблицах

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

По команде вправо Робот‑Снеговик переходит в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю.

Квадрат окружён внешними стенами. Между соседними клетками также могут находиться внутренние стены. Через стену Робот пройти не может.

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

В «угловых» клетках поля (тех, которые справа и сверху ограничены стенами) Робот не может продолжить путь, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую верхнюю клетку. При разных запусках итоговые накопленные суммы могут различаться.

Определите максимальную и минимальную итоговые суммы, которые может собрать Робот‑Снеговик, пройдя из левой нижней клетки в конечную клетку маршрута. В ответе укажите два числа — сначала максимальную сумму, затем минимальную.

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

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