Background

IOI 2009 D1T4.

Problem Description

The famous chocolatier Bonny from Plovdiv needs to cut a chocolate bar with raisins. The chocolate is a rectangle made of many identical small square pieces. These pieces are arranged along the sides of the chocolate into $N$ rows and $M$ columns, for a total of $N\times M$ pieces. Each small piece contains $1$ or more raisins, and no raisin lies on the border of a piece or crosses between two pieces.

At the beginning, the chocolate is one whole bar. Bonny needs to cut it into the $N\times M$ individual pieces described above. Since Bonny is very busy, she asks her assistant Sly Peter to help with the cutting.

Peter can only make straight cuts from one side to the other, and he must be paid for each cut. Bonny has no money, but she has enough raisins, so she offers to pay Peter with raisins. Sly Peter agrees to accept raisins, but with the following condition: each time he cuts a given piece of chocolate into two smaller pieces, he must receive a number of raisins equal to the total number of raisins in that given piece of chocolate.

Bonny wants to pay Peter as few raisins as possible. She knows the number of raisins on each of the $N\times M$ small pieces. She can choose the order in which she gives pieces of chocolate to Peter, and she can tell Peter how to cut (horizontally or vertically) and where to cut. You must help Bonny 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 small piece, computes the minimum number of raisins Bonny must pay Sly Peter.

Input Format

The first line contains two integers $N, M$ separated by spaces, representing the number of rows and columns of the chocolate.

The next $N$ lines describe the number of raisins on each small piece. The $k$-th line describes the $k$-th row of pieces. Each line contains $M$ integers separated by single spaces. These integers describe the pieces in that row from left to right. The $p$-th integer on the $k$-th line is the number of raisins $R_{k, p}$ on the piece in row $k$ and column $p$.

Output Format

Output one integer on a single line, the minimum number of raisins Bonny must pay Sly Peter.

2 3
2 7 5
1 9 5

77

Hint

Sample Explanation

One possible cutting plan with a cost of $77$ is shown below:

The first cut separates the third column from the rest of the chocolate. Bonny needs to pay Peter $29$ raisins.

Next, Bonny gives Peter the smaller piece of chocolate (which has two small pieces, each with $5$ raisins), asks Peter to cut it into two halves, and pays $10$ raisins.

After that, Bonny gives Peter the remaining largest piece (its four small pieces contain $2, 7, 1, 9$ raisins). Bonny asks Peter to cut this piece horizontally, separating the first row from the second row, and pays him $19$ raisins.

Then Bonny gives Peter the top-left piece and pays $9$ raisins. Finally, Bonny asks Peter to split the bottom-left piece and pays $10$ raisins.

Bonny’s total cost is $29 + 10 + 19 + 9 + 10 = 77$ raisins. No other cutting plan has a smaller total cost.

Constraints

• For $25\%$ of the testdata, $n,m\leq 7$.
• For $100\%$ of the testdata, $1\leq n,m\leq 50$, $1\leq R_{k, p}\leq 1000$.

Translated by ChatGPT 5