405363: GYM101915 H Buying Products

Salim (a.k.a Slango) and his wife fight all the time. When Salim came home at night, his needy wife Afaf (a.k.a Afoufe) was waiting for him at the door.

"You don't buy any products for this house! You are a lousy husband! Well guess what?? You are not coming home before buying me exactly K products, or you are sleeping on the streets!!". Said his wife.

"I'm going to buy you these products, but when you open that door you are divorced by 3 you needy wife!!". Thought Salim to him self.

Anyway, having no other option, Salim went down the stairs and headed to the nearby mall. the mall has exactly N shops. Salim knows that each of these shops has exactly 3 products (it's sales time and shops are almost empty).

However, Salim knows that buying all the 3 products of some shop will cause the owner of the shop to ask him for a huge amount of money, because he will say that the last piece is very rare. Thus, he made a rule, he will buy at most 2 products from every shop.

Salim is really tired and he just wants to go home and sleep a while in order to wake up in the morning and divorce his needy wife. Also, Salim doesn't really care about the quality of the products, he just wants to buy them with the lowest possible price. Can you help him calculate the minimum amount of money he needs to spend in order to buy his wife exactly K products, while buying at most 2 products from any given shop?

The first line contains an integer T, the number of test cases.

The first line of each test case contains 2 space separated integer N and K (1 ≤ N ≤ 1000)(1 ≤ K ≤ 2N).

N lines follows. The i^th line contains exactly 3 space separated integers denoting the prices of the 3 products at the i^th shop. (1 ≤ P_ij ≤ 10⁶)

For each test case print a single line, containing a single integer, denoting the minimum price needed to buy exactly K products from the given shops while fulfilling the above given condition.

1
3 4
1 10 300
4 5 6
1 100 1

7