E - スマートフォン (Smartphone) 解説 /

実行時間制限: 1 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

JOI 高校の生徒である葵は,1 から N までの番号が付けられた N 台のスマートフォンをレンタルしており,それぞれのスマートフォンには使用日数制限が設けられている.スマートフォン i (1 \leqq i \leqq 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 \leqq N \leqq 300\,000.
  • 1 \leqq K \leqq 10^{15}.
  • 1 \leqq A_{i} \leqq B_{i} \leqq K (1 \leqq i \leqq N).
  • 1 \leqq C_{i} \leqq B_{i} - A_{i} + 1 (1 \leqq i \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (5 点) N \leqq 1\,000,K \leqq 1\,000,B_{i} < A_{j} または B_{j} < A_{i} (1 \leqq i < j \leqq N).
  2. (10 点) C_{i} = B_{i} - A_{i} + 1 (1 \leqq i \leqq N).
  3. (10 点) N \leqq 1\,000,K \leqq 1\,000,A_{i} = 1 (1 \leqq i \leqq N).
  4. (30 点) N \leqq 1\,000,K \leqq 1\,000.
  5. (15 点) K \leqq 300\,000.
  6. (30 点) 追加の制約はない.

入力例 1

5 15
1 6 3
2 3 1
2 2 1
3 7 3
11 13 2

出力例 1

9

例えば次のようにすると,葵は 9 日 1 台以上のスマートフォンを使用することができる.この表において,〇,\times はそれぞれ該当のスマートフォンを使う日,使わない日を表す.

日数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
スマートフォン 1 〇 \times \times 〇 〇 \times
スマートフォン 2 \times 〇
スマートフォン 3 〇
スマートフォン 4 \times \times 〇 〇 〇
スマートフォン 5 \times 〇 〇

10 日以上 1 台以上のスマートフォンを使用することはできないので,9 を出力する.

この入力例は小課題 4, 5, 6 の制約を満たす.

入力例 2

4 8
1 2 2
1 3 3
1 3 3
1 5 5

出力例 2

5

例えば次のようにすると,葵は 5 日 1 台以上のスマートフォンを使用することができる.この表において,〇,\times はそれぞれ該当のスマートフォンを使う日,使わない日を表す.

日数 1 2 3 4 5 6 7 8
スマートフォン 1 〇 〇
スマートフォン 2 〇 〇 〇
スマートフォン 3 \times \times \times
スマートフォン 4 〇 〇 〇 〇 〇

6 日以上 1 台以上のスマートフォンを使用することはできないので,5 を出力する.

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす.

入力例 3

3 6
1 1 1
2 3 2
4 6 2

出力例 3

5

この入力例は小課題 1, 4, 5, 6 の制約を満たす.

入力例 4

3 7
4 6 3
4 6 1
4 6 2

出力例 4

3

この入力例は小課題 4, 5, 6 の制約を満たす.

入力例 5

15 4768558
3025257 4432949 1319859
3066618 4509446 1254699
3417684 3665318 139375
914550 2131942 1143715
729276 928089 139749
4634629 4763389 30565
3554868 4214881 168515
3206967 4721972 519481
4595561 4755647 139316
1423715 2437121 87927
2355901 3933477 584228
3076814 3150827 40891
3280648 3632366 177447
2224458 2296486 47900
2693763 4283443 832253

出力例 5

3826780

この入力例は小課題 6 の制約を満たす.


出典

JOIG 2022/2023 春季トレーニング Contest Day2 問題1