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 ith line contains exactly 3 space separated integers denoting the prices of the 3 products at the ith shop. (1 ≤ Pij ≤ 106)
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.
## Input
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 ith line contains exactly 3 space separated integers denoting the prices of the 3 products at the ith shop. (1 ≤ Pij ≤ 106)
## Output
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.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ N \in \mathbb{Z} $ be the number of friends (people), and $ K \in \mathbb{Z} $ be the total number of "clink!" sounds heard.
**Constraints**
1. $ 1 \le T \le 10^5 $
2. $ 1 \le N \le 10^4 $
3. $ 0 \le K \le 10^9 $
**Objective**
Let $ d \in \mathbb{Z}_{\ge 0} $ be the total number of drinks consumed.
Each time a person gets a new drink, they "clink" with all $ N $ other people (including those who already finished and re-poured).
The initial round: all $ N $ people get one drink and each pair clinks once → $ \binom{N}{2} $ clinks.
Each subsequent drink (by any person) adds $ N $ clinks (since they clink with all $ N $ others).
Thus, total clinks:
$$
K = \binom{N}{2} + (d - N) \cdot N
$$
Simplify:
$$
K = \frac{N(N-1)}{2} + N(d - N)
$$
$$
K = N \left( d - N + \frac{N-1}{2} \right) = N \left( d - \frac{N+1}{2} \right)
$$
Solve for $ d $:
$$
d = \frac{K}{N} + \frac{N+1}{2}
$$
**Condition for validity**:
- $ K \ge \binom{N}{2} $ (minimum clinks from initial round)
- $ \frac{K - \binom{N}{2}}{N} $ must be a non-negative integer (number of extra drinks)
- $ d $ must be an integer ≥ N
Thus, output:
If $ K < \binom{N}{2} $ or $ (K - \binom{N}{2}) \not\equiv 0 \pmod{N} $, output "Too drunk to count".
Else, output $ d = N + \frac{K - \binom{N}{2}}{N} $