Raisins

Memory limit: 128 MB

Plovdiv's famous master chocolatier Bonny needs to cut a slab of chocolate with raisins. The chocolate is a rectangular block of identical square pieces. The pieces are aligned with the edges of the chocolate, and they are arranged in rows and columns, for a total of pieces. Each piece has one or more raisins on it, and no raisins lie between or across pieces.

Initially, the chocolate is one single, monolithic block. Bonny needs to cut it into smaller and smaller blocks until finally she has cut the chocolate down to its individual pieces.

As Bonny is very busy, she needs the help of her assistant, Sly Peter, to do the cutting. Peter only makes straight line, end-to-end cuts and he wants to be paid for every single cut he makes. Bonny has no money at hand, but she has plenty of raisins left over, so she offers to pay Peter in raisins. Sly Peter agrees to this arrangement, but under the following condition: every time he cuts a given block of chocolate into two smaller blocks, he has to be paid as many raisins as there are on the block he was given.

Bonny wants to pay Peter as little as possible. She knows how many raisins there are on each of the pieces. She can choose the order in which she gives Peter any remaining blocks, and she can also tell Peter what cuts to make (horizontal or vertical) and where exactly to make them. Help Bonny decide how to cut the chocolate into individual pieces, so that she pays Sly Peter as few raisins as possible.

Task

Write a program that, given the number of raisins on each of the individual pieces, determines the minimum number of raisins that Bonny will have to pay Sly Peter.

Constraints

- the number of pieces on each side of the chocolate
- the numbers of raisins on the piece in the th row and the th column

Input

Your program must read from standard input the following data:

• The first line contains the integers and , separated by a single space.
• The next lines describe how many raisins there are on each piece of the chocolate. The th of these lines describes the th row of the chocolate. Each such line contains integers separated by single spaces. The integers describe the pieces on the corresponding row in order from left to right. The th integer on the th line (among these lines) tells you how many raisins are on the piece in the th row and the th column.

Output

Your program must write to standard output a single line containing a single integer: the minimum possible number of raisins that Bonny would have to pay Sly Peter.

Grading

For a number of tests, worth a total of 25 points, and will not exceed 7.

Przykład

For the input data:

2 3
2 7 5
1 9 5

the correct result is:

77

Explanation of the example: one possible way (out of many) to achieve a cost of 77 is as follows:

The first cut that Bonny asks Peter to make separates the third column from the rest of the chocolate. Bonny needs to pay Peter 29 raisins for this.

Then Bonny gives Peter the smaller of the two blocks: the one that has two pieces with 5 raisins each, and asks Peter to cut the block in two in exchange for 10 raisins.

After this, Bonny gives Peter the largest remaining block: the one having pieces with 2, 7, 1 and 9 raisins respectively. Bonny asks Peter to cut it horizontally, separating the first and the second row and pays him 19 raisins.

Following this, Bonny gives Peter the top-left block, paying 9 raisins. Finally, Bonny asks Peter to split the bottom-left block, paying 10 raisins.

The total cost to Bonny is raisins. No other cutting arrangement can get the chocolate cut into its 6 pieces at a smaller cost.