H. Maximal-sum Subsequence - 上海高校程序设计邀请赛（华东理工大学专场）

仪表盘所有提交榜单

单点时限: 4.0 sec

内存限制: 256 MB

给一个 $N \times N$ 的矩阵 $M$ ，可以取连续的一段数（必须是横着或者竖着或者斜着，这个矩阵是循环的，具体如下）。要求找到一个子序列，使得这个序列的和最大。

对于 $N = 8$ 的矩阵，如下序列都是合法的：

$M_{2, 1}, M_{2, 2}, M_{2, 3}, M_{2, 4}, M_{2, 5}, M_{2, 6}, M_{2, 7}, M_{2, 8}$ .
$M_{2, 2}, M_{2, 3}, M_{2, 4}$ .
$M_{2, 6}, M_{2, 7}, M_{2, 8}, M_{2, 1}, M_{2, 2}$ .
$M_{4, 3}, M_{5, 3}, M_{6, 3}, M_{7, 3}$ .
$M_{1, 2}, M_{2, 3}, M_{3, 4}, M_{4, 5}$ .
$M_{2, 4}, M_{3, 3}, M_{4, 2}, M_{5, 1}$ .
$M_{3, 3}, M_{4, 2}, M_{5, 1}, M_{1, 5}$ .
$M_{5, 6}$ .

一个元素不可取多次，取的必须是连续的一段。

可以什么都不取（即答案为 $0$ ）。

第一行一个数 $T$ $(T \leq 30)$ ，表示数据组数。

每一组数据第一行为一个正整数 $N$ $(1 \leq N \leq 1000)$ 。

接下来 $N$ 行每行 $N$ 个数表示这个矩阵。（每个元素大小在 $- 32768$ 到 $32767$ 之间）

每组数据一行表示最大的序列和。

Input

Output

样例解释：选取序列 $M_{3, 4}, M_{4, 3}, M_{1, 2}$ 。

NaN

比赛状态发生变化，点 OK 刷新。

OK

上海高校程序设计邀请赛（华东理工大学专场）