Problem Description

There is an $n \times n$ square lattice of points. The coordinate of the top-left point is $(1, 1)$, and the coordinate of the bottom-right point is $(n, n)$.

At each integer point on the lattice, there are some beans. At the point with coordinate $(i, j)$, there are $a_{i,j}$ beans.

You can place a Pac-Man: you may choose any integer point on the lattice as its initial position, and then choose one of the four directions—upper-left, lower-left, upper-right, lower-right—as its initial direction.

Pac-Man will keep moving along its initial direction, eating all beans it passes, until it hits the boundary of the lattice. Then:

1. If Pac-Man is at one of the four corners of the square lattice, it stops moving.

2. Otherwise, its moving path will be reflected with that boundary as a mirror. The figure below shows an example where a path is reflected twice:

Now you need to place two Pac-Men. Find the maximum total number of beans the two Pac-Men can eat. Note that the same bean can only be eaten once.

Input Format

The first line contains an integer $n$, representing the size of the lattice.

The next $n$ lines each contain $n$ integers. The $j$-th integer in the $i$-th line represents $a_{i,j}$.

Output Format

Output one line with one integer, representing the maximum number of beans that the two Pac-Men can eat in total.

4
20 1 19 2
3 18 4 17
16 5 15 6
7 14 8 13

132

Hint

Explanation for Sample 1

Place Pac-Men at $(1, 1)$ and $(1, 3)$, with initial directions lower-right and lower-left, respectively. Then they can eat the beans located at $(1, 1)$, $(1, 3)$, $(2, 2)$, $(2, 4)$, $(3, 1)$, $(3, 3)$, $(4, 2)$, $(4, 4)$, with a total of $132$ beans, which is the maximum. Their paths are shown as the green and red lines in the figure below:

Constraints

For $30\%$ of the testdata, $n \leq 3$.

For $60\%$ of the testdata, $n \leq 100$.

For $100\%$ of the testdata: $2 \leq n \leq 1000$, $0 \leq a_{i,j} \leq 1000$.

The testdata is jointly provided by SSerxhs and Karry5307.

Thanks to Silence_water for providing a set of hack testdata.

Translated by ChatGPT 5