Задание №18

Дан квадрат 15×15 клеток, в каждой клетке которого записано целое число. В левом верхнем углу квадрата стоит ладья. За один ход ладья может переместиться в пределах квадрата на любое количество клеток вправо или вниз (влево и вверх ладья ходить не может). Необходимо переместить ладью в правый нижний угол так, чтобы сумма чисел в клетках, в которых ладья останавливалась (включая начальную и конечную), была максимальной.
В ответе запишите максимально возможную сумму.
Исходные данные записаны в электронной таблице.
Пример входных данных (для таблицы размером 4×4):
Для указанных входных данных ответом будет число 14 (ладья проходит через клетки с числами –3, 6, 1, 7, 6, –3).