Maximum Weighted Submatrix Sum

You are given an $n \times n$ matrix, where each element is an integer in the range \([-127, 127]\). Your task is to find the submatrix (of any size) whose elements have the maximum total sum. In other words, you need to identify a submatrix such that the sum of all its elements is maximized.

Note: A submatrix is defined by choosing a contiguous block of rows and columns in the original matrix. The submatrix may consist of a single element or multiple elements.

Example:

Input:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
One of the optimal submatrices is:
9  2
-4 1
-1 8
The sum is: 9 + 2 + (-4) + 1 + (-1) + 8 = 15

Calculate and output the maximum submatrix sum.

inputFormat

The first line contains a single integer n, representing the size of the matrix. The next n lines each contain n space-separated integers, representing the rows of the matrix.

\( 1 \leq n \leq N \) (where \(N\) is a reasonable limit for the given problem and the matrix values are in the range \([-127,127]\)).

outputFormat

Output a single integer, which is the maximum submatrix sum that can be found inside the given matrix.

sample

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

15