← 返回题目列表

Codeforces · 1676/D

D. X 总和

中文机器翻译题面 查看原题

帖木儿的祖父送给他一个棋盘来练习他的棋艺。这个棋盘是一个网格$$$a$$$,有$$$n$$$行和$$$m$$$列,每个单元格上写有一个非负整数。

Timur 的挑战是在棋盘上放置一个主教,使该主教攻击的所有方格的总和最大。主教向对角线各个方向攻击,并且主教可以攻击的距离没有限制。请注意,放置主教的方格也被视为受到攻击。帮助他找到他能得到的最大金额。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 200$$$, $$$1 \leq m \leq 200$$$)。

以下 $$$n$$$ 行每行包含 $$$m$$$ 个整数,第 $$$i$$$ 行的第 $$$j$$$ 元素 $$$a_{ij}$$$ 是第 $$$i$$$ 行的第 $$$j$$$ 单元格中写入的数字 $$$(0\leq a_{ij} \leq 10^6)$$$

保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$4\cdot10^4$$$。

输出

对于每个测试用例,输出一个整数,即主教所有可能位置的最大总和。

示例

输入 #1

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

输出 #1

20
1
5
3

注意

对于这里的第一个测试用例,最佳总和是由主教处于此位置实现的: