Chop! The board has broken into 2 halves! Chop! A half has broken into 2 quarters!
Barr the bear is taking on a job that involves chopping boards. However, he is bored and hence decides to play a game while chopping. He starts out with a rectangular board with a vertical height of N units and horizontal length of M units. He then draws horizontal and vertical lines along the board 1 unit apart such that the board is divided into N*M identical square cells of unit area. Using extremely sticky honey, he sticks flower petals on the board randomly, such that each square cell contains a certain number of petals.
He intends to chop the board into N*M square pieces of unit area. However, he can only make chops along a horizontal or a vertical line on any board (hence every chop will split a board into two smaller boards). Every time he chops a board, he will add to his score the total number of petals on the board that he is chopping.
Now Barr wonders, what is the minimum score that he can get given the number of flower petals on each square cell of the board?
Input
The first line of the input contains the integers N and M (1 ≤ N, M ≤ 50), separated by a single space.
The next N lines describe how many flower petals there are on each square cell of the board. The kth of these N lines describes the kth row of the board. Each such line contains M integers separated by single spaces. The pth integer on the kth line of these lines Rk,p (1 ≤ Rk,p ≤ 1,000) tells you how many petals are on the square cell in the kth row and the pth column of the board.
Output
Write a single line containing a single integer: the minimum possible score that Barr the bear can obtain after chopping the board into
N*
M identical square pieces of unit area.
Sample Input 1
2 3
2 7 5
1 9 5
Sample Output 1
77
Explanation for Sample Output 1
One possible way (out of many) to achieve a score of 77 is as follows:
The first chop that Barr makes separates the third column from the rest of the board. Barr adds 29 to his score for this.
Then Barr takes the smaller of the two boards: the one that has two cells with 5 petals each, and chops the board in two, adding 10 to his score.
After this, Barr takes the largest remaining board: the one having cells with 2, 7, 1 and 9 petals respectively. Barr chops it horizontally, separating the first and the second row and adding 19 to his score.
Following this, Barr chops the top-left board, adding 9 to his score. Finally, Barr chops the bottom-left board, adding 10 to his score.
The total score that Barr obtains is 29 + 10 + 19 + 9 + 10 = 77. No other chopping arrangement can get the board chopped into its 6 pieces obtaining a smaller score.