Description
Teemothy never pays attention at class. He always plays Zombies vs Plants.
On a n x n garden grid, he plans to only use starfruits to shoot stars and kill the zombies.
But in this game, if a starfruit's star hit another starfruit's star (bullet), the other starfruit will die :(
Starfruit shoots star projectiles in five different directions, one up, one left, one right, one to the lower right, one to the lower left. like this:
Every grid in the garden has an integer X on it. For every starfruit you place on the garden, you get X points.
Help Teemothy to plant exactly n starfruits so that no starfruit would die (getting hit by its own bullets), and maximize his total points.
There might be no solution :D.
Input
The first line contains one integer n the length of the garden grid.
The following n lines contain n integers each, where each element is X
1 ≤ n ≤ 10
-109 ≤ X ≤ 109
Output
Print the maximum points.
If its impossible to put n starfruits in n xn grid, print "no solution".
Dont forget to put newline character.