Черепашка
Черепашка
В левом верхнем углу прямоугольной таблицы размером n * m находится черепашка. На каждой клетке таблицы разлито некоторое количество кислоты. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.
Каждый миллилитр кислоты приносит черепашке некоторое количество урона. Найдите наименьшее возможное значение урона, которое получит черепашка после прогулки по таблице.
Входные данные
В первой строке записаны два натуральных числа n и m, не превосходящие 1000 — размеры таблицы. Далее идёт n строк, каждая из которых содержит m чисел, разделённых пробелами — описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).
Выходные данные
Вывести минимальную возможную стоимость маршрута черепашки.
Пример
3 4 5 9 4 3 3 1 6 9 8 6 8 12
35
1 1 1
1