e-olymp
Competitions

December 4 - BMTK Programming School, High League

Maximum sum

Given a table with integers of size n * n. Find in it the rectangle with maximum sum. For example in the table

prb2613.gif

the rectangle with maximum sum is

prb2613_1.gif

Sum of its elements equals to 15.

Input

First number n is the size of the table. Then n2 integers are given that describes the table. It is known that n500, all numbers are integers in the range [-127, 127]. It is known that the table contains at least one nonnegative integer.

Output

Print the maximum sum in rectangle.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
Output example #1
15