#ABC188D. snuke 公司会员

snuke 公司会员

AtCoder-abc188_d

题目描述

\hspace{15pt}Snuke 公司提供多种服务,并推出了名为 Snuke Prime 的付费计划:只要每天支付 dd 日元,当天就可以不额外付费、无限次地使用公司的全部服务。

\hspace{15pt}你可以在任意一天的开始时订阅这个计划,也可以在任意一天的结束时取消订阅。每天的费用只取决于当天是否处于订阅状态:若当天订阅了计划,则支付 dd 日元,不再为任何服务付费;若当天没有订阅,则需要按实际使用的服务分别付费。

\hspace{15pt}高桥打算使用公司提供的 nn 项服务。他会从第 aia_i 天开始,一直使用第 ii 项服务到第 bib_i 天结束(包含第 bib_i 天,今天记为第 11 天)。如果不订阅 Snuke Prime,他每天使用第 ii 项服务需要支付 cic_i 日元。

\hspace{15pt}请计算高桥使用这 nn 项服务所需的最少总金额。

输入格式

\hspace{15pt}第一行输入两个整数 $n, d \left(1 \leqq n \leqq 2 \times 10^5;\ 1 \leqq d \leqq 10^9\right)$ 分别代表服务数量和订阅 Snuke Prime 每天所需的费用。

\hspace{15pt}此后 nn 行,第 ii 行输入三个整数 $a_i, b_i, c_i \left(1 \leqq a_i \leqq b_i \leqq 10^9;\ 1 \leqq c_i \leqq 10^9\right)$ 分别代表第 ii 项服务的使用区间为第 aia_i 天到第 bib_i 天(含两端),以及不订阅计划时每天使用该项服务所需的费用。

输出格式

\hspace{15pt}在一行上输出一个整数,代表高桥需要支付的最少总金额。

测试样例

2 6
1 2 4
2 2 4
10

样例 1 解释

\hspace{15pt}第 11 项服务在第 11 天和第 22 天使用,每天 44 日元;第 22 项服务只在第 22 天使用,每天 44 日元。

∙ \hspace{23pt}\bullet\,两天都不订阅:第 11 天支付 44 日元,第 22 天支付 4+4=84 + 4 = 8 日元,共 1212 日元;

∙ \hspace{23pt}\bullet\,只在第 22 天订阅:第 11 天支付 44 日元,第 22 天支付 66 日元,共 1010 日元;

∙ \hspace{23pt}\bullet\,两天都订阅:共支付 6+6=126 + 6 = 12 日元。

\hspace{15pt}因此最少需要支付 1010 日元。

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

样例 2 解释

\hspace{15pt}这里订阅费用非常高,把所有服务都按天单独付费反而更便宜。完全不订阅时所需的总金额恰好等于答案,因此最优方案之一是不订阅 Snuke Prime。

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