For a $$$ N $$$ representing a chessboard of size ($$$ N \times N $$$), there will be a $$$ N \times N $$$ matrix of integers, where value of integer present at $$$i$$$th row and $$$j$$$th column represents the score you obtain by placing queen on that position of board. Your task is to place $$$ N $$$ queens on the board such that:
The first line of input contains $$$N$$$ ($$$1 \leq N \leq 13$$$), representing the size of the board.
The next $$$N$$$ lines each contain $$$N$$$ integers, representing the score values of the matrix.
Where, the $$$i$$$-th of the next $$$N$$$ lines contains $$$a_{i1}, a_{i2}, \ldots, a_{iN}$$$ — the score values in the $$$i$$$-th row of the matrix $$$a_{ij}$$$ ($$$0 \leq a_{ij} \leq 10^4$$$).
Print a single integer — the $$$\text{maximum}$$$ possible sum of score values from a valid $$$N$$$-Queens arrangement. If no such valid placement for all queens exists then print $$$-1$$$.
Input:
4 1 2 1 2 1 1 1 1 3 3 3 3 1 1 1 1
Output:
7
Input:
5 1 2 3 4 5 5 4 3 2 1 1 2 3 4 1 1 1 1 1 2 2 2 1 1 2
Output:
16
For first sample test case the $$$\text{maximum}$$$ sum of scores is $$$7$$$ achieved by placing queens at positions: ($$$0$$$,$$$1$$$), ($$$1$$$,$$$3$$$), ($$$2$$$,$$$0$$$), ($$$3$$$,$$$2$$$).
The total sum is $$$ 2 + 1 + 3 + 1 = 7 $$$. This placement ensures no two queens share the same row, column, or diagonal, satisfying the $$$ N $$$-Queens constraint.