#1668. [语言月赛 202405] 最大的和

[语言月赛 202405] 最大的和

题目描述

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

所以她现在要给你一个 nn 行 nn 列的网格 AA,第 ii 行第 jj 列上填有一个整数 Ai,jA_{i, j}。

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

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

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

输入格式

输入共 n+1n+1 行。

第一行,一个正整数 nn,表示方阵的行数、列数。
接下来 nn 行,每行 nn 个用空格隔开的整数,其中第 ii 行第 jj 个整数表示 Ai,jA_{i, j}。

输出格式

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

样例

3
1 1 1
2 2 2
3 3 3
9
3
-1 1 2
4 0 3
1 9 2
13
3
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1
3
-100 -10 -100
-10 99999 -10
-100 -10 -100
99979

题目来源:洛谷 B3975