题目描述

小 S 喜欢连在一起的数字，如果这些数字的和很大就更好了。所以她现在要给你一个 $n$ 行 $n$ 列的网格 $A$，第 $i$ 行第 $j$ 列上填有一个整数 $A_{i,j}$。接下来你可以在 $A$ 上任取一行、一列或一条与任意对角线平行且只经过网格交叉点的直线（注意，不是线段），满足经过至少一个数字，且经过的数字之和最大。你需要告诉小 S 这个最大的数字之和。

输入格式

输入共 n+1 行。

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

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

输出格式

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

3
1 1 1
2 2 2
3 3 3

9

3
-1 1 2
4 0 3
1 9 2

13

提示

【样例输入2解释】 对于样例 2，数字之和最大的，满足条件的线如下所示：