C - ハイスコア 解説 /

実行時間制限: 6 sec / メモリ制限: 256 MB

問題文

高橋君はあるゲームが大好きである。

このゲームには N 個の遺跡があり、好きな順番に探索することができる。遺跡には 1 から N までの番号が付けられている。

ゲーム中に宝石を獲得することがある。宝石は M 種類あり、1 から M まで番号が付けられている。

遺跡を探索することで報酬として得点といくつかの宝石を入手することができる。遺跡 i (1 ≦ i ≦ N) を探索することで、得点 s_i 点を獲得し、番号が l_i 以上 r_i 以下のすべての宝石を 1 つずつ獲得する。同じ遺跡を複数回探索することはできない。

獲得した宝石は捨てることができず、またすべての種類の宝石を 1 つ以上獲得してしまうと、魔王が復活するイベントが進行する。魔王が復活する際に探索していた遺跡で得られるはずの得点は消滅してしまう。

高橋君はスコアをできるだけ高くすることを目標としており、うまく探索する遺跡を選ぶことで、魔王が復活しない状態で得られる得点の合計値を最大化したい。

考えられる最大値はいくらか。

入力

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

N M
l_1 r_1 s_1
l_2 r_2 s_2
:
l_N r_N s_N
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 100,000) と M (1 ≦ M ≦ 100,000) が空白区切りで書かれている。これは、遺跡が N 個、宝石が M 種類あることを表す。
  • 2 行目から N 行には、遺跡に関する情報を表す 3 つの整数 l_i, r_i (1 ≦ l_i ≦ r_i ≦ M), s_i (1 ≦ s_i ≦ 5,000) が与えられる。これは、遺跡 i (1 ≦ i ≦ N) を探索することで、得点 s_i 点を獲得し、番号が l_i 以上 r_i 以下のすべての宝石を 1 つずつ獲得することを表す。

配点と部分点

この問題は 101 点満点で、部分点が設定されている。

  • N ≦ 8 かつ M ≦ 8 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • N ≦ 5,000 かつ M ≦ 5,000 を満たすデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。
  • 追加制約のないデータセット 3 に正解した場合は、上記とは別に 1 点が与えられる。

出力

魔王が復活しないような探索方法として考えられるものの中で得られる得点の最大値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

4 6
1 3 30
2 3 40
3 6 25
6 6 10

出力例1

80

例えば、以下の順番に 3 つの遺跡を探索します。

  • 遺跡 1 を探索する。得点は 30 点で、宝石 1 と宝石 2 と宝石 3 を獲得する。
  • 遺跡 2 を探索する。得点は 40 点で、宝石 2 と宝石 3 を獲得する。
  • 遺跡 4 を探索する。得点は 10 点で、宝石 6 を獲得する。

最終的に獲得している宝石の種類は宝石 1 と宝石 2 と宝石 3 と宝石 6 の 4 種類なので、魔王は復活しません。合計得点は 80 点となり、これが最大値です。

入力例2

2 7
1 3 90
5 7 90

出力例2

180

すべての遺跡を探索しても魔王は復活しません。

入力例3

1 4
1 4 70

出力例3

0

魔王が復活しないように遺跡を探索することができません。