AT_abc188_d [ABC188D] Snuke Prime

[problemUrl]: https://atcoder.jp/contests/abc188/tasks/abc188_d 株式会社すぬけは様々なサービスを提供しています。 この会社は、すぬけプライムという支払いプランを用意しています。 すぬけプライムへの加入中は、$ 1 $ 日あたり $ C $ 円を支払うことで、提供される全てのサービスを追加料金の支払いなしに利用することができます。 すぬけプライムへの加入および脱退は、それぞれ $ 1 $ 日の始めおよび終わりに自由に行うことができます。 高橋くんは、この会社のサービスのうち $ N $ 個を利用しようとしています。 そのうち $ i $ 個目のサービスは、今日を $ 1 $ 日目として、$ a_i $ 日目の始めから $ b_i $ 日目の終わりまで利用する予定です。 すぬけプライムに加入していない期間中は、$ i $ 個目のサービスを利用する際に $ 1 $ 日あたり $ c_i $ 円を支払う必要があります。 サービスを利用するために高橋くんが支払う必要のある最小の合計金額を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C $ $ a_1 $ $ b_1 $ $ c_1 $ $ \vdots $ $ a_N $ $ b_N $ $ c_N $

高橋くんが支払う必要のある最小の合計金額を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ C\ \leq\ 10^9 $ - $ 1\ \leq\ a_i\ \leq\ b_i\ \leq\ 10^9 $ - $ 1\ \leq\ c_i\ \leq\ 10^9 $ - 入力に含まれる値は全て整数 ### Sample Explanation 1 $ 1 $ 番目のサービスは $ 1 $ 日目と $ 2 $ 日目に、 $ 2 $ 番目のサービスは $ 2 $ 日目に利用します。 $ 2 $ 日目のみすぬけプライムに加入すると、 $ 1 $ 日目に $ 4 $ 円、 $ 2 $ 日目に $ 6 $ 円がかかるため、高橋くんが支払う合計金額は $ 10 $ 円です。 高橋くんが支払う金額を $ 10 $ 円より少なくすることはできないため、 $ 10 $ を出力します。 ### Sample Explanation 2 すぬけプライムに全く加入しないのが最適です。