Maximum Beautiful Value Submatrix

You are given an \(N \times N\) matrix. Your task is to find the square submatrix (i.e. one with equal number of rows and columns) that has the maximum beautiful value.

The beautiful value of a square matrix is defined as follows:

[ A - B ]

where \(A\) is the sum of the elements on the main diagonal and \(B\) is the sum of the elements on the anti-diagonal. The main diagonal of a matrix consists of the elements \(a_{i, i}\) and the anti-diagonal consists of \(a_{i, L-i+1}\) when the submatrix is of size \(L\times L\).

You need to consider all possible square submatrices of the given matrix and output the maximum beautiful value.

inputFormat

The first line contains a single integer \(N\) representing the size of the matrix. Each of the following \(N\) lines contains \(N\) space-separated integers representing the rows of the matrix.

outputFormat

Output a single integer, which is the maximum beautiful value among all square submatrices of the given matrix.

sample

1
5

0