Задача #6057

Квадрат разлинован на N×N клеток (2 < N < 19). В каждой клетке лежат монеты, количество которых соответствует записанному числу. Количество монет не может быть меньше 10.

В лабиринте существуют два независимых исполнителя – Кладоискатель1 и Кладоискатель2. Каждый из них имеет две команды – влево и вниз – при выполнении которых исполнитель сдвигается либо на одну клетку влево или вниз соответственно. Движение начинается с верхней правой клетке и заканчивается с левой нижней.

Известно, что каждый исполнитель запрограммирован так, чтобы собрать максимальное количество монет на своем пути. При этом сначала на поле работает исполнитель Кладоискатель1, затем Кладоискатель2. Кладоискатель2 может проходить по клеткам из лучшего маршрута для исполнителя Кладоискатель1, однако значение в этих клетках будет равно 0.

Необходимо найти результат работы обоих исполнителей, в качестве ответа указать найденные значения – сначала для исполнителя Кладоискатель1, затем для Кладоискатель2.

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

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

Для указанных входных данных ответом должна быть пара чисел – 68 и 51.