As we all know, we live inside the matrix that is divided into ~N~ rows and ~N~ columns. An integer is written into each one of the ~N \times N~ 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 ~A~ the sum of all integers on the main diagonal of some square, and by ~B~ the sum of the other diagonal, then the beauty of that square is ~A - B~.

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 ~N~ ~(2 \le N \le 400)~, the size of the matrix.

The following ~N~ lines each contain ~N~ integers in the range ~[-1\,000, 1\,000]~, 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