# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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.

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 **A _{ij}** be the

**1 ≤ T ≤ 100****1 ≤ N ≤ 8****1 ≤ K ≤ 2N****0 ≤ A _{ij} ≤ 10^{6}**

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.

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 |

Since we can choose up to **2** different rows or columns [there are **15** possible choices], it would be optimal to choose the **3 ^{rd}** row and the

43% Solution Ratio

NirjhorEarliest,

rathijitpaponFastest, 0.3s

NirjhorLightest, 131 kB

NirjhorShortest, 1061B

Login to submit

Thanks to the rather small constraints, one simple way to approach this problem is to do recursive b...