# Practice on Toph

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

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

**j**integer on the

^{th}**i**line. Then

^{th}**A**represents the number of chocolates in the

_{ij}**j**cell of the

^{th}**i**row of the grid.

^{th}#### Constraints:

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

## 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.

## Samples

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 **3 ^{rd}** row and the

**3**column. We collect

^{rd}**3 + 6 +7 + 8 + 9 = 33**chocolates this way. We will not get a better result for any other choice of rows and columns.

#### Labib666

Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms. →