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