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

the rectangle with maximum sum is

Sum of its elements equals to **15**.

#### Input

First number **n** is the size of the table. Then `n`

integers are given that describes the table. It is known that ^{2}**n** ≤ **500**, 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.

Input example #1

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

Output example #1

15