Description

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.

Input

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.

Output

For each matrix of the input, print a line containing the least balance degree.

\\n\\n

统计

递交统计

Partition a Matrix

信息

还没有账户？

登录