Raisins

Bonny, a famous chocolate maker in Plovdiv, has made an $N \times M$ raisin chocolate bar arranged as a grid with $M$ columns and $N$ rows. Every $1 \times 1$ cell contains at least one raisin, and no raisin spans more than one cell.

Initially the chocolate is a single large block, and Bonny must split it into all $N \times M$ of its $1 \times 1$ pieces. The greedy Peter does the cutting. In one move Peter takes a single rectangular piece and cuts it into two along one straight horizontal or vertical line, demanding a reward for each cut.

Having no money, Bonny pays Peter in raisins. Peter's rule is: each time a rectangular piece is cut into two, he is paid the total number of raisins contained in that piece just before the cut. Bonny may choose which piece to cut and where to cut it.

Given the number of raisins in every cell, find the minimum total number of raisins Bonny must pay to split the whole bar into $1 \times 1$ pieces.

• The first line contains the chocolate's dimensions $N$ and $M$.
• Each of the next $N$ lines contains $M$ integers $R_{ij}$, the number of raisins in the cell at row $i$, column $j$.
• $1 \le N, M \le 50$
• $1 \le R_{ij} \le 1000$

Print, on a single line, the minimum number of raisins Bonny must pay.

This can be solved with interval dynamic programming over sub-rectangles. The cost of one cut on a rectangular piece is the total number of raisins inside it, and the two resulting pieces are then split independently. So, computing the minimum cost to fully break each rectangle into $1 \times 1$ cells from the smallest rectangles upward yields the overall answer.