To the Max

Interview

Time limit1sMemory limit128 MB

Summary

Find the contiguous rectangular subregion of an N by N integer matrix with the largest possible sum and print that sum.

Level: Medium7 of 10
Topics: Dynamic programming, Array, Prefix sum, Matrix
Solved: No attempts yet

Problem

You are given a two-dimensional array of positive and negative integers. A sub-rectangle is any contiguous rectangular region of size $1 \times 1$ or larger located within the whole array. The sum of a rectangle is the sum of all the elements inside it. In this problem, the sub-rectangle with the largest sum is called the maximal sub-rectangle.

For example, in the array

the maximal sub-rectangle is the one in the lower-left corner

 9 2
-4 1
-1 8

and its sum is 15.

Input

The input describes an $N \times N$ array of integers. The first line contains a single positive integer $N$ , the size of the square two-dimensional array. It is followed by $N^2$ integers separated by whitespace (spaces and newlines). These are the $N^2$ integers of the array in row-major order: all numbers of the first row from left to right, then all numbers of the second row from left to right, and so on. $N$ may be as large as 100. Every integer in the array lies in the range $[-127, 127]$ .

Output

Output the sum of the maximal sub-rectangle.

Examples2

Example 1

Input

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

8 0 -2

Expected output

Example 2
Input
```
1
5
```
Expected output
```
5
```