Subsequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 9 Accepted Submission(s): 1
Problem 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.
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.
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
