Problem: Art, Key, Texture

Want to try solving this problem? You can submit your code online if you log in or register.

Art, Key, Texture

Time Limit: 1.5 seconds
Memory Limit: 128 MB
Input: stdin
Output: stdout

You are Michelangelo, a budding artist in Renaissance Italy who has been employed by a wealthy noble to create the most beautiful sculpture in all the lands.

You begin with an upright marble slab which can be thought of as a H x W grid of 1 x 1 marble blocks. You then chisel away unnecessary parts of the slab until you are left with a beautiful sculpture consisting of zero or more blocks.

It is key that:

Each level of the sculpture consists of a single connected row of blocks. Having separate disconnected sections on a level is far too post-cubist squarist.
All of the blocks on each level must rest upon a block from the level below it. The bottom level must rest on the ground.

$\includegraphics[width=13cm]{arch}$

Unfortunately, your creative desires are stifled by commercial constraints: the noble you are making this sculpture for has a particular distaste for the some of your slab's marble blocks (the textures are too "swirly", you're told), and a particular penchant for others ("Yes! I like those colours"). For each marble block you have a number - possibly negative - indicating how beautiful it is. Your task is to design a sculpture where the sum of these "beauty numbers" is as large as possible.

Input

The first line of input will contain two space-separated integers H and W, representing the height and width of the marble slab.
The next H lines of input will each contain W integers representing the beauty numbers of the blocks in the slab.

Output

Output should consist of a single integer: the largest possible sum of "beauty numbers" for your sculpture.

Sample Input 1

5 6
-99 1 -99 -99 1 -99
1 -99 1 1 -99 1
-99 1 -99 1 1 -99
1 1 -99 1 1 1
1 1 1 1 -99 1

Sample Output 1

Sample Input 2

Sample Output 2

Explanation

Below are possible sculptures that maximise the sum of "beauty numbers" for each sample case above.

$\includegraphics[width=13cm]{pyramid_sample}$

Subtasks & Constraints

For all subtasks, 1 ≤ H, W ≤ 1,000 and all "beauty numbers" are integers between -1,000,000 and 1,000,000 inclusive.

For Subtask 1 (30 points), all "beauty numbers" are either -1,000,000 or 1.
For Subtask 2 (20 points), H ≤ 100 and W ≤ 25.
For Subtask 3 (25 points), H ≤ 200 and W ≤ 200.
For Subtask 4 (25 points), no further constraints apply.