eolymp
bolt
Try our new interface for solving problems
Problems

Turtle - right top

Turtle - right top

Time limit 2 seconds
Memory limit 128 MiB

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
Author Michael Medvediev