Задача #6011

(А. Калинин) Квадрат разлинован на NxN клеток (1 < N < 17). Исполнитель Зомби может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Зомби перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Зомби умирает. Перед каждым запуском Зомби в каждой клетке квадрата лежат мозги с количеством извилин от 1 до 100. Посетив клетку, Зомби забирает мозги с собой; это также относится к начальной и конечной клетке маршрута Зомби. Определите максимальную и минимальную сумму извилин, которую может собрать Зомби, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.