D - Snuke Prime

得分: $400$ 分

问题描述

Snuke Inc. 提供各种服务。
有一个名为 Snuke Prime 的付费计划可用。
在该计划中，您每天支付 $C$ 日元，即可使用公司提供的所有服务，无需支付额外费用。
您可以在任何一天开始订阅该计划，并在任何一天的结束时取消订阅。

Takahashi 计划使用 Snuke Inc. 提供的 $N$ 种服务。
他将从第 $a_i$ 天开始使用第 $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$

输出

输出 Takahashi 需要支付的最少金额。

2 6
1 2 4
2 2 4

10

他将在第一天和第二天使用第一种服务，在第二天使用第二种服务。
如果他只在第二天订阅 Snuke Prime，那么他将在第一天支付 4 日元，在第二天支付 6 日元，总共支付 10 日元。
无法使总付款金额小于 10 日元，因此我们应该输出 10。

5 1000000000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409

163089627821228

不使用 Snuke Prime 是最优选择。

5 100000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409

88206004785464