Робот хочет перейти из левого верхнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 1000 ) в правый нижний. За один шаг он может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Кроме того, проходя через каждую клетку, Робот получает несколько золотых монет (это число известно для каждой клетки).
Определите, какое минимальное количество монет может собрать Робот по пути.
Входные данные
В первой строке вводятся два натуральных числа: N и M ( 1 ≤ N , M ≤ 1000 ), разделённые пробелом. В каждой из следующих N строк записаны через пробел по M чисел, которые обозначают количество монет, получаемых Роботом при проходе через каждую клетку.
Выходные данные
В первой строке программа должна вывести наименьшее количество монет, которое может собрать Робот.
Примеры
| Входные данные |
Выходные данные |
3 3
0 2 3
2 5 7
1 2 0 |
5 |