Given a NxN array, your goal is to place N queens on it, and all of them should be safe from each other. We define the weighted sum as the total value of where your queens are placed. Please find out the second-highest weighted sum among the given array, whose value is different from the highest one.
A queen is safe from each other if there's no other queen in the same row/column/two diagonal lines.
For example, given a array:
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 1 |
The pattern with highest weighted sum is
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 1 |
1 + 1 + 1 + 3 = 6, and the second highest weighted sum is
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 1 |
1 + 1 + 1 + 2 = 5, so the answer to this example is 5.
The input contains an integer N, follow by a NxN array A.
1 <= N <= 11, |elements in A| <= 1010.
Output the second highest weighted sum of given array, followed by a newline character. If there's no such value, output "Invalid".