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

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

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.

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.

提交代码