Задачи
Черепашка - правый верх
Черепашка - правый верх
В правом верхнем углу прямоугольной таблицы размером n × m находится черепашка. На каждой клетке таблицы находится некоторое количество монет. Черепашка может перемещаться влево или вниз, при этом маршрут черепашки заканчивается в левом нижнем углу таблицы.
Найдите наибольшее количество монет, которое может собрать черепашка после прогулки по таблице.
Входные данные
В первой строке записаны два натуральных числа n и m, не превосходящие 1000 - размеры таблицы. Далее идёт n строк, каждая из которых содержит m чисел, разделённых пробелами - описание таблицы с указанием для каждой клетки количества монет на ней.
Выходные данные
Вывести максимальное количество монет, которое может собрать черепашка.
Входные данные #1
3 4 5 9 4 3 3 1 6 9 8 6 8 12
Выходные данные #1
46