問題文

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