You may notice the following program. It evaluates a kind of cost about given sequence.

calc_cost(a):
    current = 0
    cost = 0
    for (cost0, cost1, color) in a
        if current == 0
            cost += cost0 
        else
            cost += cost1
        current = color
return cost

For a sequence A consists of many triples (cost0,cost1,color), its each subsequence has a cost which calculated by this program. Alice wants to know the cost of the subsequence which is the one owns the k-th largest cost.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow.

For each test case, the first line consists two integers, n the length of sequence and k. The i-th line in the following n line consists three non-negative integers cost0, cost1 and color, where 0<=cost0,cost1<=10000 and 0<=color<=1, corresponding to the i-th triple in the sequence.

We guarantee that the sequence has at least k non-empty subsequences.

The sum of all n is no more than 400000 and the sum of all k is no more than 400000.

Output

For each case, output the answer in one line.

Example

Input

1
3 4
2 1 0
1 3 1
3 1 1

Output

3

The four sequences with the largest cost are as follow.

• calc_cost({ A_1, A_3 }) = 5.
• calc_cost({ A_1, A_2, A_3 }) = 4.
• calc_cost({ A_1, A_2 }) = 3.
• calc_cost({ A_3 }) = 3.