Counting Heads

Notice: If you are an honest guy and don't want to help the host, you can do another problem, but you cannot get the "AC".

The world wide game of counting heads is around the corner. Now the qualifier is feverishly on show. Those who pass the qualifier will have the chance to advance to the final, and may win the Super King of Counting Heads! The qualifier has two rounds, and N players will participate in it. The scores for player i in Round 1 and Round 2 are xi and yi respectively. The host will select one of a player's scores as his final result. If a player's score in Round 1(or Round 2) is selected as his final result, he will be involved in the rank of Round 1(or Round 2). The first g players involved in Round 1(and Round 2) will advance to the final. Two Rounds rank scores separately from high to low. If less than g players are involved in the rank of Round 1(or Round 2), all of them advance.

Every country hopes his players can win the title, especially the host country. How can the host select the scores so as to maximize the number of native final players according to the rules?

The first line is an integer T (T <= 200), representing the number of test cases.

In each test case, two integers N (2 <= N <= 200), g (0 <= g <= N / 2) come in the first line. N is the number of players competing in the qualifications, g is the advancing limit. Then come N lines. In each following line, there are three integers x, y, f (0 <= x, y < 10000), representing the scores of Round 1 and Round 2. If f is 1, then this is native, 0 otherwise.

(It's guaranteed that there are no two same score in one round)

Please output the result in a single line in the format of "Case x: d", in which x is the case number counted from one and d is the number of maximum native players to advance to the final in one line.

2
2 1
1 2 0
2 1 1
8 3
6 7 0
5 8 0
4 5 1
7 4 0
8 2 1
3 3 0
1 1 1
2 6 1

Case 1: 1
Case 2: 4

For the 5th, 7th, 8th players, you can select their score of Round 1 as their final result. Others select their score of Round 2 as their final result.
Then you can let four host players pass the qualifier.

dezoo

2010 ACM-ICPC Multi-University Training Contest（13）——Host by UESTC