Robot Navigation

NASA sent a remotely controlled robot to explore Mars. The real Martian terrain is very complex, but because the robot has limited memory, the terrain is simplified as an N x M grid.

Because of height differences, from its current cell the robot can move only left, right, or down. It cannot move up. The robot also never explores a cell that it has already visited.

Each cell has an exploration value. The robot starts at the upper-left cell (1, 1) and must reach the lower-right cell (N, M). Find the maximum possible sum of the values of all visited cells while following the movement rules.

The first line contains two integers N and M (1 <= N, M <= 1,000).

Each of the next N lines contains M integers. The absolute value of each integer is at most 100, and the integer represents the exploration value of that cell.

Print the maximum possible sum of the values of the visited cells.