阎小罗的Minimax

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

                                       

 

《阎王不高兴》中的阎小罗可谓人见人爱,花见花开。他的一贯开场就是:“说出来你可能不相信,我是新上任的阎王,我现在……” 自从ln看了之后,就开始在各种场合模仿,在看题的时候也不忘记来上一段,于是就有了这样的题目描述:
   “说出来你可能不相信,我是阎小罗,现在正在看题,题目意思是这样的,给你一个 n * m 的矩阵,每个小方格都有一个整数 num,矩阵的行编号从上到下为 1 ~ n,列编号从左到右为 1 ~ m,定义 ( x,y ) 表示第 x 行第 y 列的方格。现在你可以删去第 x ( 1 < x < n ) 行和第 y (1 < y < m ) 列,让原来的矩阵变成四个小矩阵,每个小的矩阵都有一个 AC 值,AC 值是当前矩阵的所有数之和。现在阎小罗想知道怎么去删除第 x 行和第 y 列,让分成的四个部分的矩阵的 AC 值中,最大值减去最小值的差值最小,阎小罗将它称作 Minimax,也就是现在的 AC 值集合中有四个小矩阵的值,AC = { AC1,AC2,AC3,AC4 },假设 AC1 是 AC 中的最大值,AC3 是 AC 中最小值,那么我们定义 M = AC1 - AC3,在所有的分割方案中,最小的那个 M 就是 Minimax,快来帮助阎小罗找到 Minimax 吧。

Input

第一行一个整数 T ,代表阎小罗矩阵的个数。( 1 <= T <= 10 )

第一行包括两个整数 n 和 m,代表阎小罗的矩阵的大小。( 3 <= n <= 300,3 <= m <= 300 )

接下来有 n 行,每一行有 m 个数,保证每个数的范围在 int 内。( 0 <= num <= 1000000000 )

Output

对于每个矩阵输出一个数,代表阎小罗想要的Minimax,占一行,行末没有多余空格。

Sample Input

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

Sample Output

4
10

Hint

Source

Mercury_Lc