Задача #6045

Квадрат разлинован на N×N клеток (2 < N < 21). В каждой клетке записано целое положительное число – количество монет.

Исполнитель Сборщик имеет две команды ВПРАВО и ВВЕРХ, которые, соответственно, перемещают его на одну клетку вправо или на одну клетку вверх. Проходя через клетку, Сборщик собирает все монеты, лежащие на ней. На поле существуют стены, обозначены жирной линией, через которые Сборщик проходить не может.

Исполнитель начинает движение в левой нижней клетке и заканчивает в правой верхней.

Какое максимальное и минимальное количество монет может собрать Сборщик, пройдя от начальной клетки до конечной?

В ответе укажите сначала максимальный, затем минимальный результат, который может быть получен исполнителем.

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

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

В качестве ответа необходимо привести сначала максимальное полученное значение, затем наименьшее.