Квадрат разлинован на N×N клеток (1 <, N <, 20). В каждой клетке находится некоторое количество монет, от 1 до 100. Исполнитель «Конь» движется с левой линии в правую линию. т. е. он может стартовать из любой клетки первого столбца и закончить маршрут в любой клетке последнего столбца таблицы. С каждой посещённой клетки исполнитель забирает с собой половину монет, если количество монет нечётное, то округление происходит в большую сторону.
Исполнитель может двигаться «ходом коня»: на две клетки вправо и на одну вверх или вниз, или на одну клетку вправо и на две клетки вверх или вниз. Определите максимальную и минимальную суммы, которые может собрать исполнитель.
Пример входных данных (для таблицы размером 5×5):
Для данного примера максимальная сумма получается при проходе коня по клеткам со значениями 54, 98, 46, 75 и 55, эта сумма равна 165. Минимальная сумма получается при проходе коня по клеткам со значениями 16, 46 и 15, эта сумма равна 39.
Ответ для данного примера: 165 39.
Исходные данные записаны в файле в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе запишите два числа: сначала максимальную сумму, затем минимальную.
