题目描述

小明要用录像机录 $N$ 个电视节目。一共有 $C$ 个电视频道，从 $1$ 到 $C$ 编号。

第 $i$ 个电视节目从时刻 $s_i$ 开始，时刻 $t_i$ 结束，在频道 $c_i$ 播出（包含开始时刻 $s_i$，不包含结束时刻 $t_i$）。同一个频道不会同时播出多个节目。

如果某个录像机在时刻 $S$ 到时刻 $T$ 录像某个频道的节目，如果接下来想用它录像其他频道的节目，需要将这个录像机接到另一个频道上，操作时间为 $D$，所以最早必须等到 $T+D$ 时刻才能开始录制其他频道的节目。

若要录下全部 $N$ 个节目，至少需要多少台录像机？

输入格式

第一行三个正整数 $N,C,D$，代表节目数、频道数和换频道需要的操作时间。

接下来 $N$ 行，每行三个正整数 $s_i,t_i,c_i$，代表第 $i$ 个节目的开始时间、结束时间和播出频道。

输出格式

输出需要的最少录像机台数。

4 4 1
1 7 2
7 8 1
8 12 1
8 12 3

2

5 4 7
1 3 1
9 11 1
10 12 4
10 14 2
18 20 3

3

9 4 30
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

4

样例说明

样例 $1$ 中，用 $1$ 号录像机从时刻 $1$ 到 $7$ 录下频道 $2$ 的一个节目。$D=1$，所以录完后最早时刻 $8$ 才能开始录制其他频道，因而不能去录频道 $1$ 在时刻 $7$ 到 $8$ 的节目。用 $1$ 号录像机从时刻 $8$ 到 $12$ 录下频道 $1$ 的节目；再用 $2$ 号录像机录下频道 $1$ 从时刻 $7$ 到 $8$ 以及频道 $3$ 从时刻 $8$ 到 $12$ 的节目。总共需要 $2$ 台录像机。

样例 $2$ 中，用 $1$ 号录像机录下频道 $1$ 的两个节目后，最早到时刻 $18$ 才能开始录制其他频道，于是从时刻 $18$ 到 $20$ 录下频道 $3$ 的节目；用 $2$ 号录像机录下频道 $2$ 的节目；用 $3$ 号录像机录下频道 $4$ 的节目。总共需要 $3$ 台录像机。

数据范围与约定

• 对于 $10\%$ 的数据，$D=0$；
• 对于 $60\%$ 的数据，$1\le C\le50$；
• 对于 $100\%$ 的数据，$1\le N\le10^5$，$1\le c_i\le C\le10^5$，$0\le D\le10^6$，$1\le s_i\le t_i\le10^6$；
• 保证同一个频道播出的节目时段不会有重叠。