Beautiful Matrix

The beauty of a square matrix is defined by the difference between the sums of its two diagonals.

Let A be the sum of the entries on the main diagonal, which runs from the top-left corner to the bottom-right corner. Let B be the sum of the entries on the other diagonal, which runs from the top-right corner to the bottom-left corner. The beauty of the matrix is A - B.

Given an N x N matrix, find the maximum beauty among all square submatrices that can be chosen from it. For a 1 x 1 submatrix, the two diagonal sums are equal, so its beauty is 0.

The first line contains the matrix size N. (2 <= N <= 400)

Each of the next N lines contains N integers separated by spaces. Every entry is between -1000 and 1000, inclusive.

Print the maximum beauty among all square submatrices of the given matrix.