e-olymp
Задачи

Черепашка

Черепашка

В левом верхнем углу прямоугольной таблицы размером n × m находится черепашка. На каждой клетке таблицы разлито некоторое количество кислоты. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

Каждый миллилитр кислоты приносит черепашке некоторое количество урона. Найдите наименьшее возможное значение урона, которое получит черепашка после прогулки по таблице.

Входные данные

В первой строке записаны два натуральных числа n и m, не превосходящие 1000 - размеры таблицы. Далее идёт n строк, каждая из которых содержит m чисел, разделённых пробелами - описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).

Выходные данные

Вывести минимальную возможную стоимость маршрута черепашки.

prb4018.gif

Лимит времени 2 секунды
Лимит использования памяти 128 MiB
Входные данные #1
3 4
5 9 4 3
3 1 6 9
8 6 8 12
Выходные данные #1
35
Входные данные #2
1 1
1
Выходные данные #2
1