Задачі
Черепашка
Черепашка
У лівому верхньому куті прямокутної таблиці розміром $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