D - Recording Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

joisinoお姉ちゃんは、録画機を用いて N 個のテレビ番組を録画しようとしています。

テレビが受信できるチャンネルは C 個あり、1 から C までの番号がついています。

joisinoお姉ちゃんの録画したいテレビ番組のうち、i 個目のテレビ番組は、時刻 s_i から時刻 t_i まで、チャンネル c_i で放送されます。(ただし時刻 s_i を含み、時刻 t_i を除く)

ただし、同じチャンネルで複数のテレビ番組が同時に放送されることはありません。

また、録画機は、あるチャンネルの時刻 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
  • c_i=c_j かつ i≠j ならば t_i≦s_j か 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 個目の録画機を用いて、時刻 1 から時刻 7 までチャンネル 2 を録画します。このとき、1 個目のテレビ番組が録画されます。また、時刻 0.5 から時刻 7 まではこの録画機を他のチャンネルの録画に使えないことに注意してください。
  • 2 個目の録画機を用いて、時刻 7 から時刻 12 までチャンネル 1 を録画します。このとき、 2 個目と 3 個目のテレビ番組が録画されます。また、時刻 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

Score : 400 points

Problem Statement

Joisino is planning to record N TV programs with recorders.

The TV can receive C channels numbered 1 through C.

The i-th program that she wants to record will be broadcast from time s_i to time t_i (including time s_i but not t_i) on Channel c_i.

Here, there will never be more than one program that are broadcast on the same channel at the same time.

When the recorder is recording a channel from time S to time T (including time S but not T), it cannot record other channels from time S-0.5 to time T (including time S-0.5 but not T).

Find the minimum number of recorders required to record the channels so that all the N programs are completely recorded.

Constraints

  • 1≤N≤10^5
  • 1≤C≤30
  • 1≤s_i<t_i≤10^5
  • 1≤c_i≤C
  • If c_i=c_j and i≠j, either t_i≤s_j or s_i≥t_j.
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N C
s_1 t_1 c_1
:
s_N t_N c_N

Output

When the minimum required number of recorders is x, print the value of x.

Sample Input 1

3 2
1 7 2
7 8 1
8 12 1

Sample Output 1

2

Two recorders can record all the programs, for example, as follows:

  • With the first recorder, record Channel 2 from time 1 to time 7. The first program will be recorded. Note that this recorder will be unable to record other channels from time 0.5 to time 7.
  • With the second recorder, record Channel 1 from time 7 to time 12. The second and third programs will be recorded. Note that this recorder will be unable to record other channels from time 6.5 to time 12.

Sample Input 2

3 4
1 3 2
3 4 4
1 4 3

Sample Output 2

3

There may be a channel where there is no program to record.

Sample Input 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

Sample Output 3

2