Coin-collecting robot vacuum

Time limit4sMemory limit128 MB

Summary

A vacuum walks 4N steps on an (N+1)x(N+1) grid of coins, must collect all four corners, and return to start; maximize coins.

Level: Medium7 of 10
Topics: Graph, Greedy, Implementation
Solved: No attempts yet

Problem

Mirko bought a smart robot vacuum at a fair. To try it out, he built a cardboard box and divided its floor into $N+1$ rows and $N+1$ columns, numbered $0$ to $N$ . He put some coins on every cell of the floor. The four corner cells $(0, 0)$ , $(0, N)$ , $(N, 0)$ and $(N, N)$ hold gold coins, and every other cell holds silver coins.

The vacuum starts on cell $(0, 0)$ . Every second it moves to one of the eight neighbouring cells, and it cannot leave the box. It picks up every coin on a cell it passes through, and a cell it enters again has no coins left. The coins on the starting cell $(0, 0)$ are picked up at the start.

Mirko ordered the vacuum to pick up all the gold coins and as many silver coins as possible, then come back to the starting cell after exactly $4N$ seconds. Write a program that computes the largest number of coins the vacuum can pick up.

Input

The first line contains an integer $N$ ( $1 \le N \le 500$ ).

Each of the next $N+1$ lines contains $N+1$ numbers of coins, the cells of one row of the floor given in column order. Every value is between $1$ and $10000$ .

Output

Print the largest number of coins the vacuum can pick up.

Examples2

Example 1
Input
```
2
1 1 1
1 10 1
1 1 1
```
Expected output
```
17
```
Example 2
Input
```
3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
```
Expected output
```
51
```