Problem Statement

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

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

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

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

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

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

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

Input

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

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$ 点が与えられる。

Output

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