Problem Description

Little S loves consecutive numbers, especially if their sum is large.

She will now give you a grid $A$ of size $n \times n$, where each cell at the $i$-th row and $j$-th column contains an integer $A_{i, j}$.

You can choose any row, any column, or any line parallel to the diagonals that only passes through the grid intersections (note, it is not a segment) from $A$, provided it passes through at least one number, and the sum of the numbers it passes through is maximized.

If you are confused by the above description, please refer to the sample explanation for clarification.

You need to tell Little S the maximum sum of the numbers.

Input Format

The input consists of $n+1$ lines.

The first line contains a positive integer $n$, representing the number of rows and columns of the square matrix.
The next $n$ lines each contain $n$ integers separated by spaces, where the $i$-th line and $j$-th integer represent $A_{i, j}$.

Output Format

Output a single integer, which is the maximum sum of the numbers.

Sample Input and Output

Input Sample #1

3
1 1 1
2 2 2
3 3 3

Output Sample #1

9

Input Sample #2

3
-1 1 2
4 0 3
1 9 2

Output Sample #2

13

Input Sample #3

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

Output Sample #3

-1

Input Sample #4

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

Output Sample #4

99979

Notes

Sample 1 Explanation

For Sample $1$, it is easy to see that the sum of the numbers in the $3$-rd row is the largest, which is $3 + 3 + 3 = 9$.

Sample 2 Explanation

For Sample $2$, the line with the maximum sum of numbers that meets the conditions is shown below:

In this case, the sum is $4 + 9 = 13$.

Note that lines parallel to the diagonals can only pass through grid intersections, so it is not possible to take $4, 1, 9$ or $4, 1, 9, 2$ simultaneously.

Sample 3 Explanation

Taking a line that passes through only one $-1$ is the maximum. Note that it is not allowed to select no numbers at all.

Sample 4 Explanation

Clearly, taking a diagonal line is not optimal, so you can only choose the middle row or column, and the answer is $-10 + 99999 - 10 = 99979$.

Data Range

For the first $30\%$ of the data, it is guaranteed that either $A_{1, 1}$ or $A_{n, n}$ is the only non-negative integer in the grid.
For the next $20\%$ of the data, it is guaranteed that each row has the same numbers, and the sum of the numbers in the last row is the maximum.
For the next $20\%$ of the data, it is guaranteed that each row has the same numbers, and there are no negative numbers in the grid.
For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 2 \times 10^3, -10^5 \leq A_{i, j} \leq 10^5$.

见题面 Input 部分

见题面 Output 部分