Given an M * N matrix consisted of non-negative elements, you may partition it into three parts with two straight line segments. The line segments cannot go through any element of the matrix and they must be parallel to the row or the column of the matrix, but they need not to be parallel to each other. Each of the three parts is a non-empty matrix, which means it contains at least one element. We define the value of a matrix as the sum of all elements in it. We denote the values of the three remaining matrices as X, Y, Z, and the balance degree as |X - Y| + |Y - Z| + |Z - X|, where |.| means the absolute value. Among all ways of partition, there is one, which has the least balance degree. Your task is to decide what the least balance degree is.
输入解释
The input will consist of several test cases. For each test case, two integers M and N are given in the first line, indicating the number of rows and columns of the matrix; each of the following M lines contains N integers, indicating the matrix. The input is terminated by a single line with two zeros. You may assume that 2 <= M, N <= 500 and all elements of the matrix are integers in the range [0, 65535].
There may be some blank lines between test cases.
输出解释
For each matrix of the input, print a line containing the least balance degree.
输入样例
3 3
9 8 7
6 5 4
3 2 1
0 0
输出样例
10
提示
The three partitions are: {9, 8}, {6, 5, 3, 2}, {7, 4, 1}, whose values are: 9 + 8 = 17, 6 + 5 + 3 + 2 = 16, 7 + 4 + 1 = 12. The corresponding balance degree is: |17 - 16| + |16 - 12| + |12 - 17| = 10. This is the least balance degree you can get.