# 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

40% Solution Ratio

NirjhorEarliest,

rathijitpaponFastest, 0.3s

NirjhorLightest, 131 kB

NirjhorShortest, 1061B

Login to submit