# 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.

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

7

### Sample Input 2

5 4
7 1 1 2
-5 2 -6 3
-3 -8 1 -4
4 2 -2 -3
-1 3 1 1

### Sample Output 2

10

### Explanation

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

### 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.