Description

To better prepare for NOIP 2013, several girls from the computer club, LYQ, ZSC, and ZHQ, thought that besides a computer lab, they also needed exercise. So they decided to ask the principal for an after-class sports field for the computer club. Hearing that they were all top students in the computer club, the principal did not agree immediately, but first gave them a math problem, and told them: the area of the sports field you can get equals the largest number you can find.

The principal first gives them an $n \times n$ matrix. The task is to find the maximum weighted rectangle in the matrix. Each element of the matrix has a weight defined on the set of integers. Find a rectangle (of unrestricted size) such that the sum of all elements it contains is maximized. Each element of the matrix belongs to $[-127, 127]$. For example:

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

In the lower-left corner:

9  2
-4  1
-1  8

the sum is $15$.

The girls found it a bit difficult, so they asked the meticulous HZH and TZY from the computer club to help with the calculation. Unfortunately, their answers were different. Since this concerns land allocation, we must be precise. Can you compute the rectangle in the principal’s matrix with the maximum weighted sum?

Input Format

The first line contains $n$. Then follow $n$ lines with $n$ integers each, forming the matrix.

Output Format

Output the maximum sum of any rectangle (submatrix).

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

15

Hint

$1 \leq n \le 120$.

Translated by ChatGPT 5