Subsequence

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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

For a sequence A consists of many triples ($cost_0, cost_1$, 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 $cost_0, cost_1$ and color, where 0 <= $cost_0, cost_1$ <= 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.

Sample Input

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

Sample Output

3
Hint

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

提交代码