Given a M × M array of positive and negative integers, find the sub-rectangle with the largest sum. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. The input to the program is the value of M followed by the array itself.

Input:

First line contains M ( 1 <= M<= 100 )

Next M lines contains M elements each, describing the matrix A ( -100 <= A[i][j] <= 100 )

Output:

The Maximum Sum (Followed by a '\n' which is just for a newline, no need to display)

Sample Cases:

Input:

4

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

Output:

15

how to solve this one!!!