Raisins#290
Plovdiv’s famous master chocolatier Bonny wants to cut a slab of chocolate with raisins. The chocolate is a rectangular block made up of identical square pieces. The pieces are aligned with the edges of the chocolate: there are rows and columns, giving a total of N \times M pieces. Each piece has one or more raisins on it, with no raisins lying between or across pieces.
Initially, the chocolate is a single, monolithic block. Bonny must cut it into smaller and smaller blocks until she ends up with its N \times M individual pieces.
Bonny is very busy, so she asks her assistant Peter to do the cutting. Peter only makes straight, end-to-end cuts and wants to be paid for every cut he makes. Bonny has no money at hand, but she has plenty of leftover raisins, so she offers to pay Peter in raisins. Peter agrees, but under the following condition: every time he cuts a block of chocolate into two smaller blocks, he must be paid as many raisins as there are on the block being cut.
Bonny wants to pay Peter as few raisins as possible. She knows how many raisins are on each of the N \times M pieces. She can choose the order in which the remaining blocks are cut, and she can instruct Peter where to make each cut (horizontal or vertical) and at which position.
Help Bonny determine how to cut the chocolate into individual pieces so that she pays Peter the minimum possible number of raisins.
Task
Write a program that, given the number of raisins on each individual piece, determines the minimum number of raisins that Bonny must pay Peter.
The first line contains two integers and (1 \leq N, M \leq 50) — the number of rows and columns.
Each of the next lines contains integers, denoting the number of raisins on each piece in that row (from left to right). Specifically, the -th integer in the -th line, R_{k,p} (1 \leq R_{k,p} \leq 1000), indicates the number of raisins on the piece in row and column .
Output a single integer: the minimum possible number of raisins that Bonny would have to pay Peter.
Example 1