Grades

Interview

Time limit1sMemory limit1024 MB

Summary

Given an N by N grid of scores, find the largest pocket money left after deleting one rectangular sub-table, where each score adds (score minus 50).

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

Statement

Juku has taken several tests at school, and each test is graded from $0 \ldots 100$ points.

Juku's grandfather gives him pocket money based on his grades. He treats a score above 50 as a good grade and a score below 50 as a bad grade. Specifically, he adds the part of each score above 50 to the pocket money and subtracts the part below 50. For example, with scores 35, 42, 81, and 100, Juku receives $(35-50)+(42-50)+(81-50)+(100-50) = -15-8+31+50 = 58$ euros. A test scored exactly 50 does not change the pocket money.

The teacher records Juku's scores in an Excel table with $N$ rows and $N$ columns, so Juku has $N^2$ scores in total. Juku can access the table once and change his grades. He selects one rectangular sub-table (it may be empty, that is, contain zero cells) and deletes all the grades in it.

Find the maximum amount of pocket money Juku can receive after such a deletion.

Input

The first line contains an integer $N$ ( $2 \le N \le 300$ ), the side length of the teacher's table.

Each of the next $N$ lines contains $N$ integers from $0$ to $100$ , separated by spaces. These are Juku's grades.

Output

Print one integer: the maximum amount of pocket money Juku can receive.

Examples2

Example 1
Input
```
3
80 90 90
100 5 60
90 60 10
```
Expected output
```
200
```

Example 2

Input

4
100 100 100 100
100 2 2 100
100 90 90 100
100 2 2 100

Expected output