Description

There is a two-dimensional array containing both positive and negative numbers. A submatrix refers to any contiguous subarray within this 2D array with dimensions of 1×1 or larger. The sum of a submatrix is the total of all its elements. In this problem, the submatrix with the largest sum is referred to as the maximum submatrix.

For example:

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

The maximum submatrix for this array is:

9 2
-4 1
-1 8

Its sum is 15.

Input Format

The input contains multiple test cases. The first line of each test case is a positive integer N (1 ≤ N ≤ 100), representing the size of the square matrix. The next N lines each contain N integers, representing the elements of the array, with values ranging from [-127, 127].

Output Format

Output the maximum submatrix sum.

```input1 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 ``` ```output1 15 ``` ## Source

CodesOnline