题目描述

小 S 喜欢连在一起的数字，如果这些数字的和很大就更好了。

所以她现在要给你一个 $n$ 行 $n$ 列的网格 $A$，第 $i$ 行第 $j$ 列上填有一个整数 $A_{i,j}$。

接下来你可以在 $A$ 上任取一行、一列或一条与任意对角线平行且只经过网格交叉点的直线（注意，不是线段），满足经过至少一个数字，且经过的数字之和最大。

如果对上面的表述有疑惑，请参考样例解释辅助理解。

你需要告诉小 S 这个最大的数字之和。

输入格式

输入共 $n+1$ 行。

第一行，一个正整数 $n$，表示方阵的行数、列数。

接下来 $n$ 行，每行 $n$ 个用空格隔开的整数，其中第 $i$ 行第 $j$ 个整数表示 $A_{i,j}$。

输出格式

输出一行一个整数，表示最大的数字之和。

样例 #1

样例输入 #1

3
1 1 1
2 2 2
3 3 3

样例输出 #1

9

样例 #2

样例输入 #2

3
-1 1 2
4 0 3
1 9 2

样例输出 #2

13

样例 #3

样例输入 #3

3
-1 -1 -1
-1 -1 -1
-1 -1 -1

样例输出 #3

-1

样例 #4

样例输入 #4

3
-100 -10 -100
-10 99999 -10
-100 -10 -100

样例输出 #4

99979

提示

样例解释

• 样例 2：和最大的线经过 $4$ 和 $9$，和为 $13$。因为直线只能经过网格交叉点，所以无法同时取到 $4,1,9$；
• 样例 3：只能取某条只经过一个 $-1$ 的直线，答案为 $-1$，不允许一个数字都不选；
• 样例 4：斜线都不优，取中间一行 $99979$。

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 2\times 10^3$，$-10^5\leq A_{i,j}\leq 10^5$。