上海高校程序设计邀请赛（华东理工大学专场）
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
1 4 8 6 6 1 -3 4 0 5 4 2 1 9 1 -9 9 -2
Output
24
提示
样例解释：选取序列 $M_{3,4}, M_{4,3}, M_{1,2}$。
通知
比赛状态发生变化，点 OK 刷新。
通知