Snuke Prime

题目描述

Snuke 公司提供各种服务。
有一种名为 Snuke Prime 的付费计划可供选择。
在该计划中，通过每天支付 $C$ 日元（日本的货币），您可以使用公司提供的所有服务而无需额外费用。
您可以在任意一天的开始时订阅此计划，并在任意一天的结束时取消订阅。 Takahashi 将使用公司提供的 $N$ 项服务中的若干项。
他将从第 $a_i$ 天的开始使用第 $i$ 项服务，直到第 $b_i$ 天的结束，其中今天为第 1 天。
如果不订阅 Snuke Prime，他必须为使用第 $i$ 项服务每天支付 $c_i$ 日元。
求 Takahashi 使用这些服务所需支付的最少总金额。

输入格式

输入从标准输入按照以下格式给出： $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

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

163089627821228

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$ 输入中的所有值均为整数。他将在第 $1$ 天和第 $2$ 天使用第 $1$ 项服务，并在第 $2$ 天使用第 $2$ 项服务。
如果他仅在第 $2$ 天订阅 Snuke Prime，第 $1$ 天他将支付 4 日元，第 $2$ 天他将支付 6 日元，总计 10 日元。
不可能使总支付少于 10 日元，因此我们应输出 10 日元。
最优策略是不订阅 Snuke Prime。

标签: AtCoder|abc188D

来源

AtCoder|abc188D