分数: 400 点
问题陈述
Snuke Inc. 提供各种服务。
可以使用名为 Snuke Prime 的付款计划。
在此计划中,通过支付 C 日元(日本货币)每天,您可以使用公司提供的所有服务,无需额外费用。
您可以在任何一天开始时开始订阅此计划,并在任何一天结束时取消订阅。
高桥将要使用 N 公司提供的服务。
他将使用 i- 从开始的那些服务 a_i- 第天直到结束 b_i-第天,今天是第一天。
如果没有订阅 Snuke Prime,他必须付费 c_i 每天使用日元 i第服务。
找出 Takahashi 使用服务必须支付的最低总金额。
约束
- 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-st 服务 1-st 和 2第几天,以及 2-nd 服务 2- 第三天。
如果他仅在 2- 第一天,他会付款 4 日元上 1-st 天和 6 日元上 2- 第 天,总共 10 日元。
付款总额不可能少于 10 日元,所以我们应该打印 10.
示例输入 2
5 1000000000 583563238 820642330 44577 136809000 653199778 90962 54601291 785892285 50554 5797762 453599267 65697 468677897 916692569 87409
示例输出 2
163089627821228
最好不要使用 Snuke Prime。
示例输入 3
5 100000 583563238 820642330 44577 136809000 653199778 90962 54601291 785892285 50554 5797762 453599267 65697 468677897 916692569 87409
示例输出 3
88206004785464