AT_abc188_d [ABC188D] Snuke Prime

题目描述

株式会社すぬけ提供了多种服务。
该公司推出了一种名为“すぬけプライム”的支付方案。
在加入すぬけプライム期间，每天只需支付 $C$ 日元，即可无限制地使用公司提供的所有服务，无需额外付费。
加入或退出すぬけプライム可以在任意一天的开始或结束时自由进行。

高桥君打算使用该公司提供的 $N$ 项服务。
其中，第 $i$ 项服务计划从第 $a_i$ 天的开始到第 $b_i$ 天的结束使用（今天为第 $1$ 天）。
在未加入すぬけプライム的期间，使用第 $i$ 项服务时，每天需支付 $c_i$ 日元。

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

输入格式

输入通过标准输入按以下格式给出。

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

输出格式

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

输入输出样例 #1

输入 #1

2 6
1 2 4
2 2 4

输出 #1

10

输入输出样例 #2

输入 #2

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

输出 #2

163089627821228

输入输出样例 #3

输入 #3

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

输出 #3

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

第 $1$ 项服务在第 $1$ 天和第 $2$ 天使用，第 $2$ 项服务在第 $2$ 天使用。仅在第 $2$ 天加入すぬけプライム时，第 $1$ 天需支付 $4$ 日元，第 $2$ 天需支付 $6$ 日元，因此高桥君需支付的总金额为 $10$ 日元。无法再减少支付金额，因此输出 $10$。

样例解释 2

完全不加入すぬけプライム是最优选择。

由 ChatGPT 4.1 翻译