程序设计在线评测(Online Judge)


问题 1050. -- 巧克力

1050: 巧克力

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 5
[提交][状态][讨论版]

题目描述

布欧可以把人变成巧克力吃了来增加他的能量,也有可能减少。

现在布欧变了n*m个巧克力,并把巧克力排成一个n*m的矩形,现在布欧想选择一个子矩形,把这个子矩形吃了来增加他的能量,可他不知道选哪个才能使他的能量增加值p最大,布欧也可以选择一个都不吃,这样p = 0

现在布欧要你告诉他p的最大值,不然他就先把你变成巧克力吃了!

输入

第一行:一个整数T 代表测试个数,

接着T组测试数据。

 

对每组测试数据:

第一行:n m 两个整数

接着n行每行m个空格隔开的整数a(i,j)代表对应巧克力的能量值(注意可以是负数,吃了能量减少)

 

 

1<=n,m<=300

-1000<= a(i,j) <= 1000

输出

T

每行一个整数 p

样例输入

3
3 3
1 -1 4
2 -2 3
3 -10 1
3 3
-1 -1 -1
-1 -1 -1
-1 -1 -1
3 3
1 1 -10
-1 1 -10
1 1 -10

样例输出

8
0
4

提示

请使用scanf输入。


第一组数据吃


4


3


1


第二组数据一个也不吃


第三组数据吃


1 1


-1 1


1 1

来源

[提交][状态][讨论版]