/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
株式会社すぬけは様々なサービスを提供しています。
この会社は、すぬけプライムという支払いプランを用意しています。
すぬけプライムへの加入中は、1 日あたり C 円を支払うことで、提供される全てのサービスを追加料金の支払いなしに利用することができます。
すぬけプライムへの加入および脱退は、それぞれ 1 日の始めおよび終わりに自由に行うことができます。
高橋くんは、この会社のサービスのうち N 個を利用しようとしています。
そのうち i 個目のサービスは、今日を 1 日目として、a_i 日目の始めから b_i 日目の終わりまで利用する予定です。
すぬけプライムに加入していない期間中は、i 個目のサービスを利用する際に 1 日あたり c_i 円を支払う必要があります。
サービスを利用するために高橋くんが支払う必要のある最小の合計金額を求めてください。
制約
- 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
- 入力に含まれる値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N C a_1 b_1 c_1 \vdots a_N b_N c_N
出力
高橋くんが支払う必要のある最小の合計金額を出力せよ。
入力例 1
2 6 1 2 4 2 2 4
出力例 1
10
1 番目のサービスは 1 日目と 2 日目に、 2 番目のサービスは 2 日目に利用します。
2 日目のみすぬけプライムに加入すると、 1 日目に 4 円、 2 日目に 6 円がかかるため、高橋くんが支払う合計金額は 10 円です。
高橋くんが支払う金額を 10 円より少なくすることはできないため、 10 を出力します。
入力例 2
5 1000000000 583563238 820642330 44577 136809000 653199778 90962 54601291 785892285 50554 5797762 453599267 65697 468677897 916692569 87409
出力例 2
163089627821228
すぬけプライムに全く加入しないのが最適です。
入力例 3
5 100000 583563238 820642330 44577 136809000 653199778 90962 54601291 785892285 50554 5797762 453599267 65697 468677897 916692569 87409
出力例 3
88206004785464
Score : 400 points
Problem Statement
Snuke Inc. offers various kinds of services.
A payment plan called Snuke Prime is available.
In this plan, by paying C yen (the currency of Japan) per day, you can use all services offered by the company without additional fees.
You can start your subscription to this plan at the beginning of any day and cancel your subscription at the end of any day.
Takahashi is going to use N of the services offered by the company.
He will use the i-th of those services from the beginning of the a_i-th day until the end of the b_i-th day, where today is the first day.
Without a subscription to Snuke Prime, he has to pay c_i yen per day to use the i-th service.
Find the minimum total amount of money Takahashi has to pay to use the services.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C a_1 b_1 c_1 \vdots a_N b_N c_N
Output
Print the minimum total amount of money Takahashi has to pay.
Sample Input 1
2 6 1 2 4 2 2 4
Sample Output 1
10
He will use the 1-st service on the 1-st and 2-nd days, and the 2-nd service on the 2-nd day.
If he subscribes to Snuke Prime only on the 2-nd day, he will pay 4 yen on the 1-st day and 6 yen on the 2-nd day, for a total of 10 yen.
It is impossible to make the total payment less than 10 yen, so we should print 10.
Sample Input 2
5 1000000000 583563238 820642330 44577 136809000 653199778 90962 54601291 785892285 50554 5797762 453599267 65697 468677897 916692569 87409
Sample Output 2
163089627821228
It is optimal to do without Snuke Prime.
Sample Input 3
5 100000 583563238 820642330 44577 136809000 653199778 90962 54601291 785892285 50554 5797762 453599267 65697 468677897 916692569 87409
Sample Output 3
88206004785464