Two Pac‐Men Bean Feast

You are given an n × n grid of points. The top‐left point has coordinates \((1, 1)\) and the bottom‐right point has coordinates \((n, n)\). At each integer grid point \((i,j)\) there are \(a_{i,j}\) beans.

You can place a Pac–Man in the grid. When placing a Pac–Man you must choose (i) an initial grid point (which can be any point) and (ii) an initial moving direction, which must be one of the four diagonal directions: top–left, top–right, bottom–left, or bottom–right. Once placed, the Pac–Man will start moving in its initial diagonal direction and will eat all the beans at every point it visits. Its movement continues indefinitely in the following way:

1. The Pac–Man moves in its current direction until it reaches the boundary of the grid.
2. When it reaches an edge, if its current position is at one of the four corners of the grid then it stops moving; otherwise, its direction is reflected against that boundary (as if the edge were a mirror) and it continues moving.

Note that if a Pac–Man visits the same cell more than once, the beans in that cell are eaten only on the first visit.

Your task is to place two Pac–Men (each with an independently chosen starting cell and initial direction) so that the total number of beans eaten (i.e. the sum of beans in the union of the cells visited by the two Pac–Men) is maximized. Output this maximum total.

The law of reflection ensures that when the Pac–Man hits a boundary (but is not at a corner), the corresponding component of the moving direction is reversed; that is, if the Pac–Man is at \((x,y)\) moving in direction \((dx,dy)\) and if \(x+dx\) is out of the range \([1,n]\) then set \(dx=-dx\) (and similarly for \(y+dy\)). After reflecting, the Pac–Man immediately moves one step in its new direction.

All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(n\) (the size of the grid).

Then \(n\) lines follow. The \(i\)th line contains \(n\) integers \(a_{i,1}, a_{i,2}, \ldots, a_{i,n}\), where \(a_{i,j}\) represents the number of beans at cell \((i,j)\).

\(1 \leq n \leq 20\) (for instance) and the bean counts can be assumed to be nonnegative integers.

outputFormat

Output a single integer: the maximum total number of beans that can be eaten by the two Pac–Men combined.

sample

2
1 2
3 4

10