问题描述

在方形果园里，勤劳的果农老张规划了一个 $n$ 行 $n$ 列的整齐种植区域。每一个种植位置上都种着一棵果树，第 $i$ 行第 $j$ 列的果树在今年收获季节的产量为整数 $A_{i, j}$ 千克。

老张想要估算果园里沿特定方向的果树总产量最大值，以便规划后续的采摘和运输方案。他规定，可以选取任意一行、任意一列，或者沿着与果园正方形区域任意对角线平行（即斜向）的直线上的果树（这条直线至少要经过一棵果树），计算这些果树上果实的总产量，如下图所示：

上图是从斜着走相同颜色的果园。

请你帮忙计算出按照上述规则，能够得到的最大总产量是多少，帮助老张提前做好准备。

输入格式

输入内容共 $n + 1$ 行。

第一行，输入一个正整数 $n$，它代表果园种植区域的行数和列数。

接下来的 $n$ 行，每行都有 $n$ 个用空格隔开的整数，其中第 $i$ 行第 $j$ 个整数表示对应位置果树上的产量 $A_{i, j}$（单位：千克）。

输出格式

输出一行，包含一个整数，这个整数就是按照规则计算出的最大总产量（单位：千克）。

样例输入

3
1 1 1
2 2 2
3 3 3

样例输出

9

样例输入

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

样例输出

-1

数据范围

对于 $30\%$ 的数据，$1 \le n \le 1000$，$1 \le A_{i, j} \le 10^4$。保证选取某一行或者某一列就能得到最大的总产量。

对于 $70\%$ 的数据，$1 \le n \le 1000$，$1 \le A_{i, j} \le 10^5$。

对于 $100\%$ 的数据，$1 \le n \le 1000$，$-10^8 \le A_{i, j} \le 10^8$。