题目描述

给定一个由非负元素组成的M * N矩阵,您可以将其分成三个部分,并有两个直线段。行段不能遍历矩阵的任何元素,它们必须与矩阵的行或列平行,但它们不必彼此平行。三个部分中的每一个都是非空矩阵,这意味着它至少包含一个元素。我们将矩阵的值定义为其中所有元素的总和。我们将其余三个矩阵的值表示为$X,Y,Z,$平衡度为$|X - Y| + |Y - Z| + |Z - X|$,其中$|.|$表示绝对值。在所有分区的方式中,有一种,平衡度最低。你的任务是决定什么是最不平衡的学位。

输入

输入将包含几个测试用例。对于每个测试用例,在第一行中给出两个整数M和N,指示矩阵的行数和列数;以下每个M行都包含N个整数,表示矩阵。输入由一条带有两个零的单行终止。您可以假设$2 <= M,N <= 500$和矩阵的所有元素都是$[0,65535]$范围内的整数。

测试用例之间可能有一些空白线。

输出

对于输入的每个矩阵,打印包含最小平衡度的线。 输入数 1

3 3
9 8 7
6 5 4
3 2 1
0 0

输出数位 1

10

提示

三个分区是:${9,8},{6,5,3,2},{7,4,1}$,其值是:$9 + 8 = 17,6 + 5 + 3 + 2 = 16,7 + 4 + 1 = 12$。相应的平衡度是:$|17-16|+ |16-12|+|+12-17|=10。$这是你能得到的最少的平衡度。 来源

POJ 月刊,c0500301036