Snuke 高级会员

题目描述

株式会社 Snuke 提供各种服务。

这家公司准备了名为「Snuke Prime」的支付方案。

在加入 Snuke Prime 期间，每天支付 $C$ 日元，就可以使用所提供的所有服务，无需额外付费。

加入和退出 Snuke Prime 可以分别在一天的开始和结束时自由进行。

高桥君打算使用该公司的 $N$ 项服务。

其中第 $i$ 项服务计划从以今天为第 $1$ 天的 $a_i$ 日天的开始，用到 $b_i$ 日天的结束。

在没有加入 Snuke Prime 的期间，使用第 $i$ 项服务时每天需要支付 $c_i$ 日元。

求高桥君为了使用这些服务所需支付的最小总金额。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出高桥君需要支付的最小总金额。

样例

2 6
1 2 4
2 2 4

10

第 $1$ 项服务在第 $1$ 天和第 $2$ 天使用，第 $2$ 项服务在第 $2$ 天使用。

只在第 $2$ 天加入 Snuke Prime 时，第 $1$ 天花费 $4$ 日元，第 $2$ 天花费 $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

数据范围

• $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$
• 输入中包含的值均为整数