← 返回题目列表

AtCoder · abc080_d

D. 录音

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

Joisino 正在计划录制 N 带有录音机的电视节目。

电视可以接收 C 频道编号 1 通过 C.

的 i她要录制的节目从时间开始播出 s_i 到时间 t_i (包括时间 s_i 但不是 频道上的 t_i) c_i.

在这里,同一频道上永远不会同时播放多个节目。

当录音机正在录制某个频道时 S 到时间 T (包括时间 S 但不是 频道上的 T),无法从时间开始录制其他通道 S-0.5 到时间 T (包括时间 S-0.5 但不是 频道上的 T).

求出记录通道所需的最少记录器数量,以便所有通道 N 节目已录制完毕。

约束

  • 1≤N≤10^5
  • 1≤C≤30
  • 1≤s_i<t_i≤10^5
  • 1≤c_i≤C
  • If c_i=c_j 和 i≠j,或者 t_i≤s_j or s_i≥t_j.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N C
s_1 t_1 c_1
:
s_N t_N c_N

输出

当所需的最小记录器数量为 x,打印值 x.


示例输入 1

3 2
1 7 2
7 8 1
8 12 1

示例输出 1

2

两台录像机可以录制所有节目,例如如下:

  • 用第一台录音机,录制频道 2 从时间 1 到时间 7。将录制第一个节目。请注意,此录音机将无法录制其他频道 0.5 到时间 7.
  • 用第二个录音机,记录频道 1 从时间 7 到时间 12。第二个和第三个节目将被录制。请注意,此录音机将无法录制其他频道 6.5 到时间 12.

示例输入 2

3 4
1 3 2
3 4 4
1 4 3

示例输出 2

3

可能某个频道没有可录制的节目。


示例输入 3

9 4
56 60 4
33 37 2
89 90 3
32 43 1
67 68 3
49 51 3
31 32 3
70 71 1
11 12 3

示例输出 3

2