Квадрат разлинован на N N клеток (1 < N < 25). Исполнитель Ферзь может перемещаться по клеткам, выполняя за одно перемещение движение на любое количество клеток вправо,вниз или вниз по диагонали. При попытке выхода за границу квадрата Ферзь разрушается. Перед каждым запуском Ферзь в каждой клетке квадрата лежит монета достоинством от -100 до 100. Посетив клетку, Ферзь забирает монету с собой; это также относится к начальной и конечной клетке маршрута Ферзь.

Откройте файл. Определите максимальную денежную сумму, которую может собрать Ферзь, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите одно число - максимальную сумму, которую может собрать Ферзь, пройдя из левой верхней клетки в правую нижнюю.

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