Задание выполняется с использованием прилагаемых файлов

Квадрат разлинован на клеток . Исполнитель Ладья может перемещаться по клеткам, выполняя за одно перемещение движение на любое количество клеток вправо или вверх. При попытке выхода за границу квадрата Ладья разрушается. Перед каждым запуском Ладьи в каждой клетке квадрата лежит монета достоинством от до . Посетив клетку, Ладья забирает монету с собой; это также относится к начальной и конечной клетке маршрута Ладьи.

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

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