Задача #6054

Квадрат разлинован на N×N клеток (2 < N < 19). В каждой клетке записано целое число, соответствующее значению в ячейке таблицы.

Исполнитель Змейка может перемещаться по нечетным линиям вправо или вниз, по четным – влево или вниз. При прохождении через клетку к счету исполнителя прибавляется записанное в клетке число. Змейка начинает движение в левом верхнем углу поля и не может выходить за его пределы (пустые ячейки таблицы).

Какой максимальный и минимальный счет может быть получен в результате работы исполнителя?

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

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

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