Рабочее место участника

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 NxN 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.

The first line of input contains the positive integer `N` (`2\ ≤\ N\ ≤\ 400`), the size of the matrix. The following `N` lines each contain `N` integers in the range `[-1000,\ 1000]`, the elements of the matrix.

The only line of output must contain the maximum beauty of a square found in the matrix.

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