Osvaldo and his friend Rogelio are looking to buy some paints to add some color to his house. He knows each color he uses to paint his house will add a beauty $$$x$$$ (not necessarily positive) to the house. The store is having a special offer; the paints are placed in a square matrix, and if you buy a set of paints such that you can draw a spiral in the matrix beginning in one of the corners and filling the whole matrix, where the set is contiguous in the spiral, the paint is free! Since Rogelio is in a hurry to start training for ICPC, they have asked you to help them find the best sum of beauty one can add to the house if the paint is free, notice you can decide to buy no paints.
On the first line a number $$$N$$$ ($$$1\leq N \leq 1000$$$), the length of the matrix. In the next $$$N$$$ lines, $$$N$$$ numbers $$$a_{i,j}$$$ ($$$-10^7 \leq a_{i,j} \leq 10^7$$$) indicating the beauty that color will add to the house if bought.
Just a number $$$X$$$ the best sum of beauty you can get added to the house such that the paints are free.
2-1 32 -5
4
31 -2 43 8 -65 1 -10
20
A spiral is a traversal of the matrix that is a reflection or rotation of one similar to this:
| 1 | 12 | 11 | 10 |
| 2 | 13 | 16 | 9 |
| 3 | 14 | 15 | 8 |
| 4 | 5 | 6 | 7 |
This is the specific case for $$$n = 4$$$
