Chocolate Cutting with Raisins Payment

Bonny, the famous chocolate master of Plovdiv, has a rectangular chocolate bar composed of N rows and M columns of square pieces, each containing one or more raisins. The raisins are completely contained within each square (none on the borders or straddling two pieces).

Initially the chocolate is a single, intact block. Bonny needs to cut it into N×M individual pieces. Her assistant, Sly Peter, is tasked with making the cuts. However, Peter can only make straight cuts that go from one end of a piece to the opposite end, and he demands payment for each cut equal to the total number of raisins on the chocolate piece being cut at that time.

Bonny has enough raisins to pay but wants to minimize the total amount she pays Peter. Knowing the number of raisins on each of the N×M pieces, Bonny can decide in which order to hand over pieces to Peter and can specify how (horizontal or vertical cuts) and where to cut.

Your task is to compute the minimum number of raisins Bonny must pay to end up with individual pieces.

Note: If a subrectangle consists of a single square, no cut is needed and thus no payment is made.

The cost function, if a cut divides a subrectangle into two parts, is given by:

\( dp(x_1,y_1,x_2,y_2) = \min_{\substack{x=x_1\ldots x_2-1}} (dp(x_1,y_1,x,y_2)+dp(x+1,y_1,x_2,y_2)) \) or over vertical cuts \( \min_{\substack{y=y_1\ldots y_2-1}} (dp(x_1,y_1,x_2,y)+dp(x_1,y+1,x_2,y_2)) \) plus the sum of raisins in the subrectangle.

inputFormat

The first line contains two integers, N and M (1 ≤ N, M ≤ small numbers), representing the number of rows and columns of the chocolate bar.

Then follow N lines, each containing M space-separated integers. Each integer indicates the number of raisins on that particular square of chocolate.

outputFormat

Output a single integer, the minimum number of raisins Bonny must pay to cut the chocolate bar into individual pieces.

sample

1 1
5

0