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

```7
```

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

```10
```

### Explanation

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

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.

Privacy statement
`Page generated: 25 March 2023,  6:13pm AEDT`