#ABC188D. snuke 公司会员
snuke 公司会员
AtCoder-abc188_d
题目描述
Snuke 公司提供多种服务,并推出了名为 Snuke Prime 的付费计划:只要每天支付 日元,当天就可以不额外付费、无限次地使用公司的全部服务。
你可以在任意一天的开始时订阅这个计划,也可以在任意一天的结束时取消订阅。每天的费用只取决于当天是否处于订阅状态:若当天订阅了计划,则支付 日元,不再为任何服务付费;若当天没有订阅,则需要按实际使用的服务分别付费。
高桥打算使用公司提供的 项服务。他会从第 天开始,一直使用第 项服务到第 天结束(包含第 天,今天记为第 天)。如果不订阅 Snuke Prime,他每天使用第 项服务需要支付 日元。
请计算高桥使用这 项服务所需的最少总金额。
输入格式
第一行输入两个整数 $n, d \left(1 \leqq n \leqq 2 \times 10^5;\ 1 \leqq d \leqq 10^9\right)$ 分别代表服务数量和订阅 Snuke Prime 每天所需的费用。
此后 行,第 行输入三个整数 $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)$ 分别代表第 项服务的使用区间为第 天到第 天(含两端),以及不订阅计划时每天使用该项服务所需的费用。
输出格式
在一行上输出一个整数,代表高桥需要支付的最少总金额。
测试样例
2 6
1 2 4
2 2 4
10
样例 1 解释
第 项服务在第 天和第 天使用,每天 日元;第 项服务只在第 天使用,每天 日元。
两天都不订阅:第 天支付 日元,第 天支付 日元,共 日元;
只在第 天订阅:第 天支付 日元,第 天支付 日元,共 日元;
两天都订阅:共支付 日元。
因此最少需要支付 日元。
5 1000000000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409
163089627821228
样例 2 解释
这里订阅费用非常高,把所有服务都按天单独付费反而更便宜。完全不订阅时所需的总金额恰好等于答案,因此最优方案之一是不订阅 Snuke Prime。
5 100000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409
88206004785464