28023번 - Smartphone 서브태스크다국어

JOI 高校の生徒である葵は，$1$ から $N$ までの番号が付けられた $N$ 台のスマートフォンをレンタルしてお り，それぞれのスマートフォンには使用日数制限が設けられている．スマートフォン $i$ ($1 ≦ i ≦ N$) は，明日 を $1$ 日目としたとき，$A_i$ 日目から $B_i$ 日目までの $B_i - A_i + 1$ 日のうち $1$ 日単位で最大 $C_i$ 日まで選んで使用 することができる．このとき，使用する日は連続していなくても構わない．

今レンタルしているスマートフォンはすべて $K + 1$ 日目に返却しなくてはならない．そこで，葵はスマー トフォンを最大限使用するために明日から $K$ 日分の使用計画を立てようと思ったが，難しかったため，あ なたに頼むことにした．

葵がレンタルしているスマートフォンの台数 $N$，使用計画を立てる日数 $K$，それぞれのスマートフォンの 使用日数制限が与えられる．葵が $K$ 日の間で $1$ 台以上のスマートフォンを使用することのできる最大日数 を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

$N$ $K$

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_N$ $B_N$ $C_N$

標準出力に，葵が $1$ 台以上のスマートフォンを使用することのできる最大日数を $1$ 行で出力せよ．

• $1 ≦ N ≦ 300\,000$．
• $1 ≦ K ≦ 10^{15}$．
• $1 ≦ A_i ≦ B_i ≦ K$ ($1 ≦ i ≦ N$)．
• $1 ≦ C_i ≦ B_i - A_i + 1$ ($1 ≦ i ≦ N$)．
• 入力される値はすべて整数である．