Description

Given an $N \times N$ matrix, find the square submatrix (i.e., with equal height and width) that has the maximum beauty value.

Define the beauty value of a matrix as follows: let $A$ be the sum of the numbers on the main diagonal of this matrix, and let $B$ be the sum of the numbers on the other diagonal. Then the beauty value is $A - B$.

Input Format

The first line contains a positive integer $N$.

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

Output Format

Output one integer on a single line, the maximum beauty value.

2
1 -2
4 5

4

3
1 2 3
4 5 6
7 8 9

0

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

5

Hint

Constraints

For $100\%$ of the testdata, $1 \le N \le 400$, and each matrix element $\in [-10^3,10^3]$.

Notes

The scoring of this problem follows the original COCI settings. The full score is $80$.

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

Translated by ChatGPT 5