题目描述

Snuke 公司提供各种服务。
有一种名为 Snuke Prime 的付费计划可供选择。
在该计划中，您每天支付 C 日元（日本货币），即可使用公司提供的所有服务而无需额外费用。
您可以在任意一天的开始订阅该计划，并在任意一天的结束取消订阅。

Takahashi 打算使用公司提供的 N 种服务。
他将从第 a_i 天开始使用这些服务，直到第 b_i 天结束，其中今天是第一天。
如果不订阅 Snuke Prime，他每天使用第 i 种服务需要支付 c_i 日元。

请找出 Takahashi 使用这些服务需要支付的最小总金额。

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le C \le 10^9$
• $1 \le a_i \le b_i \le 10^9$
• $1 \le c_i \le 10^9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出:

$N$ $C$ $a_1$ $b_1$ $c_1$ $\vdots$ $a_N$ $b_N$ $c_N$

输出

打印 Takahashi 使用这些服务需要支付的最小总金额。

示例输入 1

2 6
1 2 4
2 2 4

示例输出 1

10

他将在第 1 天和第 2 天使用第 1 种服务，并在第 2 天使用第 2 种服务。
如果他仅在第 2 天订阅 Snuke Prime，他将在第 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

最佳方案是不订阅 Snuke Prime。

示例输入 3

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

示例输出 3

88206004785464