题目描述

小 Z 最近学习了矩阵的概念，特别是矩阵的"迹"。对于一个 $N \times N$ 的正方形矩阵 $A$，它的"迹"是指所有主对角线元素的和，也就是所有满足 $i = j$ 的元素 $A_{i,j}$ 的和。

现在，小 Z 有一个 $N \times N$ 的矩阵 $A$，他想从这个矩阵中截取一个正方形子矩阵。所谓正方形子矩阵，就是从原矩阵中选取连续的行和连续的列，形成一个 $l \times l$ 的正方形区域（其中 $1 \leq l \leq N$）。

具体来说，一个起始位置为 $(r, c)$，大小为 $l \times l$ 的子矩阵 $B$ 定义为：

$$B_{i,j} = A_{r+i-1, c+j-1} \quad \text{其中} \quad 1 \leq i,j \leq l$$

小 Z 想知道，在所有可能的正方形子矩阵中，"迹"的最大值是多少？

输入格式

第一行包含一个整数 $N$，表示矩阵的大小

接下来 $N$ 行，每行包含 $N$ 个空格分隔的整数，表示矩阵 $A$ 的一行

输出格式

对于每个测试用例，输出一行，包含一个整数，表示所有正方形子矩阵中迹的最大值。

输入输出样例

3
1 2 5
6 3 4
2 7 1

13

样例 $\tt \#1$ 说明

在 $3 \times 3$ 的矩阵中，我们可以截取不同的正方形子矩阵：

• 大小为 $1 \times 1$ 的子矩阵：迹就是该元素本身
• 大小为 $2 \times 2$ 的子矩阵：迹是左上角和右下角元素的和
• 大小为 $3 \times 3$ 的子矩阵：迹是三个对角线元素的和

通过计算，我们发现从第2行第1列开始的 $2 \times 2$ 子矩阵：

6 3
2 7

其迹为 $6 + 7 = 13$，这是所有子矩阵中迹最大的。

数据范围

• $2 \leq N \leq 100$。
• $1 \leq A_{i,j} \leq 100$。