As we all know, we live inside the matrix that is divided into rows and columns. An integer is written into each one of the cells of the matrix. In order to leave the matrix, we must find the most beautiful square (square-shaped sub-matrix) contained in the matrix.
If we denote by the sum of all integers on the main diagonal of some square, and by the sum of the other diagonal, then the beauty of that square is .
Note: The main diagonal of a square is the diagonal that runs from the top left corner to the bottom right corner.
Input Specification
The first line of input contains the positive integer , the size of the matrix.
The following lines each contain integers in the range , the elements of the matrix.
Output Specification
The only line of output must contain the maximum beauty of a square found in the matrix.
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
Comments