Coin-collecting robot vacuum

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.

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$.

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