Задача #824

(Г. Золотухин) Квадрат разлинован на N×N клеток (1 < N < 20). В каждой клетке находится некоторое количество монет, от 1 до 100. Исполнитель «Конь» движется с левой линии в правую линию. т. е. он может стартовать из любой клетки первого столбца и закончить маршрут в любой клетке последнего столбца таблицы. С каждой посещённой клетки исполнитель забирает с собой половину монет, если количество монет нечётное, то округление происходит в большую сторону.

Исполнитель может двигаться «ходом коня»: на две клетки вправо и на одну вверх или вниз, или на одну клетку вправо и на две клетки вверх или вниз. Определите максимальную и минимальную суммы, которые может собрать исполнитель.

Пример входных данных (для таблицы размером 5×5):

Для данного примера максимальная сумма получается при проходе коня по клеткам со значениями 54, 98, 46, 75 и 55; эта сумма равна 165. Минимальная сумма получается при проходе коня по клеткам со значениями 16, 46 и 15; эта сумма равна 39.

Ответ для данного примера: 165 39.

Исходные данные записаны в файле в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе запишите два числа: сначала максимальную сумму, затем минимальную.