Description
Mr Bean likes to play chess,
He likes the queen piece the most because it can move in every direction.
Every grid in the chessboard has an integer X on it. For every queen he places on the chessboard, he gets X points.
He wants to place 8 queens on the chessboard such that no queen threatens one another , where each row and collumn and diagonal of the board contains exactly one queen.
And the sum of the numbers on the chessboard selected is the minimum.
Input
The first line contains one integer K the number of boards.
The following 8 lines contain 8 integers each, where each element is Xij
1 ≤ K ≤ 20
0 ≤ Xij ≤ 10000
Output
Print the minimum points.
Dont forget to put newline character.