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