#CF4034. 象的摆放

象的摆放

题目描述

光头强的祖父送给他一个棋盘来练习他的棋艺。这个棋盘是一个有 nn 行和 mm 列的网格 aa,每个单元格上都有一个非负整数。

光头强的挑战是在棋盘上放置一个象,使象能攻击的所有网格的分值和达到最大。象向四个对角攻击,且可以攻击的距离没有限制。注意,象所在的网格也被认为受到了攻击。帮助光头强找到他能得到的最大总分。

输入格式

输入的第一行包含单个整数 t(1t1000)t(1≤t≤1000) 表示测试用例的数量。测试用例描述如下。

每个测试用例的第一行包含整数 n,m(1n2001m200)n,m(1≤n≤200,1≤m≤200)

以下 nn 行各包含 mm 个整数,第 ii 行的第 jj 个元素 aija_{ij} 是写入第 ii 行第 jj 个单元格中的数字 (0aij106)(0≤a_{ij}≤10^6)

保证所有测试用例的 n×mn\times m 总和不超过 4×1044\times 10^4

输出格式

对于每个测试用例,输出一个整数,表示象能够攻击到的网格的分值和的最大值。

测试样例

4
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0
20
1
5
3

样例说明

对于这里的第一个测试用例,象处于这个位置时,可以获得最大和:

image