Robot Navigation

Time limit1sMemory limit512 MB

Summary
Given an N x M grid, find the maximum sum path from top-left to bottom-right moving only left, right, or down without revisiting cells.
Level

Medium6 of 10

Topics
Dynamic programming, Matrix, Greedy
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples1

  1. Example 1

    Input
    5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15
    Expected output
    319