Problems
Turtle - right top
Turtle - right top
There is a turtle in the right top corner of rectangular table of size n × m. Each cell of the table contains some amount of coins. Turtle can move left or down, its route terminates in the left bottom cell of the table.
Find the maximum possible number of coins that the turtle can pick up after a walk through the table.
Input data
First line contains two positive integers n and m, no more than 1000 - the sizes of the table. Then n lines are given, each contains m integers - the description of the table, each number gives the number of coins in the cell.
Output data
Print the maximum possible income for the turtle.
Examples
Input example #1
3 4 5 9 4 3 3 1 6 9 8 6 8 12
Output example #1
46