Задачи
Черепашка
Черепашка
В левом верхнем углу прямоугольной таблицы размером $n * m$ находится черепашка. На каждой клетке таблицы разлито некоторое количество кислоты. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.
Каждый миллилитр кислоты приносит черепашке некоторое количество урона. Найдите наименьшее возможное значение урона, которое получит черепашка после прогулки по таблице.
\InputFile
В первой строке записаны два натуральных числа $n$ и $m$, не превосходящие $1000$ --- размеры таблицы. Далее идёт $n$ строк, каждая из которых содержит $m$ чисел, разделённых пробелами --- описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).
\OutputFile
Вывести минимальную возможную стоимость маршрута черепашки.
\includegraphics{https://static.e-olymp.com/content/d5/d5015f56069ea666cf0b4eac4fcf1e95ceeaa98e.gif}
Входные данные #1
3 4 5 9 4 3 3 1 6 9 8 6 8 12
Выходные данные #1
35
Входные данные #2
1 1 1
Выходные данные #2
1