Apple Tree

Interview

Time limit1sMemory limit512 MB

Summary

Given an N by N grid of profits, find the K by K square subgrid with the largest sum.

Level: Medium4 of 10
Topics: Prefix sum, Array, Brute force, Implementation
Solved: No attempts yet

Problem

There is a square orchard of size $N \times N$ , and $N \times N$ apple trees are planted in every cell on a $1 \times 1$ grid.

Farmer Hyeonggon wants to harvest apples in the fall, but the landowner Sinyoung informed him: "You may harvest and take away the apple trees only in a square of size $K \times K$ within the orchard. Here $K$ is an integer with $1 \le K \le N$ ! I will eat the rest! Haha!"

Harvesting a single apple tree brings in profit from the apples and loss from labor cost at the same time.

So Hyeonggon recorded the total profit, the profit from the apples plus the labor cost, as a two-dimensional array indexed by the tree's coordinates.

You want to give poor cute Hyeonggon the maximum total profit, away from the cruel landowner Sinyoung. Help Hyeonggon!

Input

The first line gives the size of the orchard $N$ . ( $1 \le N \le 300$ )

From the second line to the $N + 1$ -th line, the total profit obtained by harvesting that tree is given.

The total profit is an integer with $-1{,}000 \le$ value $\le 1{,}000$ .

Output

Print the maximum value on the first line.

Examples2

Example 1

Input

4
-1 -2 -3 -4
5 6 7 8
9 10 11 12
-13 -14 -15 -16

Expected output

Example 2
Input
```
3
-1 -1 -1
-1 -1 -1
-1 -1 -1
```
Expected output
```
-1
```