F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 4548. -- 小奇的糖果

4548: 小奇的糖果

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 515  Solved: 229
[Submit][Status][Discuss]

Description

有 N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾

起多少糖果,使得获得的糖果并不包含所有的颜色。

Input

包含多组测试数据,第一行输入一个正整数 T 表示测试数据组数。

接下来 T 组测试数据,对于每组测试数据,第一行输入两个正整数 N、K,分别表示点数和颜色数。
接下来 N 行,每行描述一个点,前两个数 x, y (|x|, |y| ≤ 2^30 - 1) 描述点的位置,最后一个数 z (1 ≤ z ≤
 k) 描述点的颜色。
对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3

Output

对于每组数据在一行内输出一个非负整数 ans,表示答案

Sample Input

1
10 3
1 2 3
2 1 1
2 4 2
3 5 3
4 4 2
5 1 2
6 3 1
6 7 1
7 2 3
9 4 2

Sample Output

5

HINT

Source

By Hzwer

[Submit][Status][Discuss]

HOME Back