In the lecture before, we've learned how to solve 8 queens problem.
In this problem, you need solve a similar problems. But the girdsize of the board is now n x n rather than 8 x 8. And what you have to place is stars rather than queens. In origin 8 queens problem we know the attacking range of a queen is like the word "米" where the queen is in the center. And the attacking range of a star is like the word "大" where the star is in the center. For example consider n = 8 and place a star at (3, 3), the cells marked O will be attacked by the star.
..O.....
OOSOOOOO
.O.O....
O...O...
.....O..
......O.
.......O
........
For each cell (i, j) there is an interger aij on it. If you place a star on (i, j), you will score aij points.
Your task is to place exactly n stars such that every star would not attacks another star and then maximize the sum of points you score. There may be no placement which meets the condition. Note you can only place at most one star on a cell.
The first line contains one integer n (1 ≤ n ≤ 10) – the side-length of the board.
The following n lines contain n integers each, the j-th element in the i+1-th line is aij (-109 ≤ aij ≤ 109).
Output the maximum points which meet the condition. If there is no such placement which meets the condition, output "no solution" instead.
And then output a newline('\n').