P1719 Maximum Weighted Rectangle

To better prepare for NOIP 2013, several girls from the computer group—LYQ, ZSC, and ZHQ—believed that they needed not only a computer room but also physical exercise. So they decided to apply to the principal for an extracurricular sports field for their group. Hearing that they were all skilled members of the computer group, the principal did not immediately agree but first gave them a math problem. He told them that the area of the sports field they could obtain would be the largest number they could find from the problem. The principal gave them an $n \times n$ matrix where each element has an integer weight. They need to find the maximum weighted rectangle in the matrix (i.e., find a rectangle of any size such that the sum of all elements it contains is maximized) and output the sum of all elements in that rectangle. The weight of each element in the matrix is within the range $[-127, 127]$. The girls found this a bit challenging, so they sought help from two meticulous young members of the computer group, HZH and TZY. Unfortunately, their answers differed. We cannot afford to be sloppy when it comes to land matters. Can you help calculate the maximum weighted rectangle in the principal's matrix?

The first line contains a positive integer $n$. The next $n$ lines each contain $n$ integers, representing the given matrix.

Output a single integer representing the sum of all elements in the maximum weighted rectangle of the matrix.

### Explanation The maximum weighted rectangle in this matrix is: ```text 9 2 -4 1 -1 8 ``` Their sum is $15$. ### Data Range For $100\%$ of the data, $1 \le n \le 120$. Translated by Kimi K2 Thinking.