For the 3rd game of the annual Squirrel Games, you are given the following scenario. A squirrel is in a forest. The forest is represented by an \(n \times n\) grid and the positions inside of it are represented by \((i,j)\) \((1 \leq i \leq n, 1 \leq j \leq n)\). You can choose the start of its journey from any position in the forest and you have to choose an integer \(x\). Now the squirrel must travel to all the positions that have a Manhattan distance less than or equal to \(x\), if any of those positions is out of the forest you cannot choose that \(x\). You have to maximise \(x\). Every time the squirrel travels to a position it collects all the nuts that are on that position. Print the maximum number of nuts it can collect.

Manhattan distance between two positions \((x_1,y_1)\) and \((x_2,y_2)\) is defined as \(|x_1 - x_2| + |y_1 - y_2|\).

The first line contains a single integer \(n\) \((3 \leq n \leq 100)\) — described in the statement.
Then \(n\) lines follow, each of them contains \(n\) integers \(a_{ij}\) \((0 \leq a_{ij} \leq 100)\) — the \(j\)-th integer on the \(i\)-th line denotes the number of nuts on the \(i\)-th row and \(j\)-th column.

\(3 \leq n \leq 100\)
\(0 \leq a_{ij} \leq 100\)

For each test case, print a single integer — the maximum number of nuts the squirrel can collect.

Input copy	Output copy
3 1 2 3 4 5 6 7 8 9	25

Input copy	Output copy
4 1 0 3 1 0 1 6 2 0 7 9 8 4 3 8 0	38

In the first sample, the squirrel starts its journey from the position \((2,2)\) and \(x\) is 1. It collects nuts from \((1,2), (2,1), (2,2), (2,3), (3,2)\).

 In the second sample, the squirrel starts its journey from the position \((3,3)\) and \(x\) is 1. It collects nuts from \((2,3), (3,2), (3,3), (3,4), (4,3)\).