Beautiful Matrix

Time limit1sMemory limit128 MB

Summary

Given an N x N matrix (N up to 400), find the maximum difference between the main diagonal sum and anti-diagonal sum over all possible square submatrices.

Level: Medium6 of 10
Topics: Matrix, Prefix sum, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
2 
1 -2
4 5
```
Expected output
```
4
```
Example 2
Input
```
3
1 2 3
4 5 6
7 8 9
```
Expected output
```
0
```
Example 3
Input
```
3
-3 4 5
7 9 -2
1 0 -6
```
Expected output
```
5
```