← 返回题目列表

AtCoder · abc188_d

D. 潜龙 Prime

中文机器翻译题面 查看原题

分数: 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