Problem Description

Given an $N \times N$ matrix, find the submatrix with the maximum beauty value, where the submatrix is a square, meaning its length and width are equal.

The beauty value of a matrix is defined as follows: Let $A$ be the sum of the numbers on the main diagonal, and $B$ be the sum of the numbers on the other diagonal. The beauty value of the matrix is $A - B$.

Input Format

The first line of input contains a positive integer $N$.

The next $N$ lines each contain $N$ integers, representing the matrix.

Output Format

Output a single integer, which is the maximum beauty value.

Sample Input and Output

Sample Input #1

2
1 -2
4 5

Sample Output #1

4

Sample Input #2

3
1 2 3
4 5 6
7 8 9

Sample Output #2

0

Sample Input #3

3
-3 4 5
7 9 -2
1 0 -6

Sample Output #3

5

Notes

Data Range

For $100\%$ of the data, $1 \le N \le 400$, and the matrix elements are in the range $[-10^3, 10^3]$.

Notes

This problem's score is set according to the original COCI contest, with a full score of $80$.

The problem is translated from COCI2011-2012 CONTEST #1 T2 MATRIX.

见题面 Input 部分

见题面 Output 部分