Alice in Candyland
Alice came up with a new game. In this game called "Candy Quest", there is a NxN size 2D grid. In each of the cells in this grid, there are some chocolates. Alice is given an integer K. She can choose up to K different rows and columns. Then she gets to collect all the chocolates from the cells in those rows and columns.
Alice can collect candies only once from a cell. So, even if a cell belongs to both a selected row and a selected column, she can only collect candies once from that cell.
Given the number of chocolates in each cell and the value of K, tell Alice what is the maximum number of chocolates she can collect if she plays optimally.
Input
The first line of input contains an integer T. Here, T is the number of test cases. T test cases follow.
The first line of each test case contains two space separated integers, N and K which have been defined in the statement above.
Each of the following N lines contains N space separated integers. Let Aij be the jth integer on the ith line. Then Aij represents the number of chocolates in the jth cell of the ith row of the grid.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 8
1 ≤ K ≤ 2N
0 ≤ Aij ≤ 106
Output
For each test case, print one line of output which consists of one integer: the maximum number of chocolates Alice can collect if she plays "Candy Quest" optimally.
Sample
| Input | Output |
|---|---|
2 3 2 1 2 3 2 0 6 7 8 9 3 2 1 2 3 2 0 6 7 8 9 | 33 33 |
Explanation:
Since we can choose up to 2 different rows or columns [there are 15 possible choices], it would be optimal to choose the 3rd row and the 3rd column. We collect 3 + 6 +7 + 8 + 9 = 33 chocolates this way. We will not get a better result for any other choice of rows and columns.
