ある会社が、惑星間宇宙船の燃料として用いる反物質を生成する技術を試験しています。反物質は、反応炉で特別な実験を行うことによって生成されます。

反物質を生成する実験には、既知の種類が $n$ 種類あります。種類 $i$ の実験を行うと、反応炉の出力容器に $l_i$ グラム以上 $r_i$ グラム以下の反物質が追加されます。安全上の理由から、容器に $a$ グラムを超える反物質を蓄積することは禁止されています。

種類 $i$ の実験を行う費用は $c_i$ であり、生成された反物質の価値は 1 グラム当たり $10^9$ です。

実験を行った後、容器内に $t$ グラムの反物質があり、反応炉で実験を行うためにかかった費用の合計が $s$ であるとすると、利益は $(t\cdot10^9-s)$ で定義されます。会社は、確実に得られる利益を最大化する実験戦略を開発する必要があります。

戦略は、これまでの実験結果に応じて、次にどの種類の実験を行うか、あるいはこれ以上の実験を終了するかを決定します。実験結果がどのようなものであっても、第一に反応炉の容器内の反物質が $a$ グラム以下であり、第二に利益が $x$ 以上となるとき、その戦略は利益 $x$ を確実に得られるといいます。

例えば、実験が 1 種類しかなく、生成される反物質が $4$ グラム以上 $6$ グラム以下、実験費用が $10$、容器の容量が $17$ グラムであるとします。この実験を 2 回行った後、容器内の反物質は $8$ グラム以上 $12$ グラム以下となります。$12$ グラムが得られた場合、それ以上実験を行うことはできません。$6$ グラムの反物質が生成されると、容器の容量を超える可能性があるためです。それ以外の場合は 3 回目の実験を行うことができ、反物質は $12$ グラム以上 $17$ グラム以下となります。最悪の場合は実験を 3 回行い、費用の合計は $30$、利益は $(12\cdot10^9-30)=11\,999\,999\,970$ となります。

確実に得られる最大の利益 $x$ を求めるプログラムを作成してください。

入力

入力の最初の行には、実験の種類数 $n$ と、容器内で許される反物質の最大量 $a$ を表す 2 つの整数が含まれます ($1\le n\le100$, $1\le a\le2\,000\,000$)。

続く $n$ 行にはそれぞれ、種類 $i$ の実験で得られる反物質の最小量、最大量、およびその種類の実験の費用を表す 3 つの整数 $l_i,r_i,c_i$ が、この順に含まれます ($1\le l_i\le r_i\le a$, $1\le c_i\le100$)。

出力

確実に得られる最大の利益 $x$ を表す整数を 1 つ出力してください。

入出力例

入力 1

1 17
4 6 10

出力 1

11999999970

入力 2

2 11
2 2 100
3 5 5

出力 2

9999999890

小課題