题目背景

小 R 有一个 $n \times n$ 的数字网格，她想找到一条直线，使得这条直线上所有数字的和最大。

题目描述

给定一个 $n$ 行 $n$ 列的整数网格 $A$，第 $i$ 行第 $j$ 列的数为 $A_{i, j}$。

你可以在网格上任取一行、一列、或一条与某条对角线平行且只经过网格交叉点的直线（不是线段），要求该直线经过至少一个数字，求这些数字之和的最大值。

输入格式

第一行，一个正整数 $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

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

-1

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

99979

提示

样例 1 解释

第 $3$ 行数字之和最大，$3 + 3 + 3 = 9$。

样例 2 解释

斜线 $A_{2,1} + A_{3,2} = 4 + 9 = 13$ 为最大值。

样例 3 解释

所有数都是 $-1$，取一个数即可，答案为 $-1$。

样例 4 解释

取中间行 $-10 + 99999 - 10 = 99979$ 为最大值。

数据范围

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