P7472 [NOI Online 2021 Junior] Pac-Man

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.

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 one line with one integer, representing the maximum number of beans that the two Pac-Men can eat in total.

### 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](https://www.luogu.com.cn/user/29826) and [Karry5307](https://www.luogu.com.cn/user/60990). Thanks to [Silence_water](https://www.luogu.com.cn/user/338630) for providing a set of hack testdata. Translated by ChatGPT 5