Задание №18

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