101883: [AtCoder]ABC188 D - Snuke Prime

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

Snuke Inc. offers various kinds of services.
A payment plan called Snuke Prime is available.
In this plan, by paying $C$ yen (the currency of Japan) per day, you can use all services offered by the company without additional fees.
You can start your subscription to this plan at the beginning of any day and cancel your subscription at the end of any day.

Takahashi is going to use $N$ of the services offered by the company.
He will use the $i$-th of those services from the beginning of the $a_i$-th day until the end of the $b_i$-th day, where today is the first day.
Without a subscription to Snuke Prime, he has to pay $c_i$ yen per day to use the $i$-th service.

Find the minimum total amount of money Takahashi has to pay to use the services.

Constraints

  • $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$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum total amount of money Takahashi has to pay.


Sample Input 1

2 6
1 2 4
2 2 4

Sample Output 1

10

He will use the $1$-st service on the $1$-st and $2$-nd days, and the $2$-nd service on the $2$-nd day.
If he subscribes to Snuke Prime only on the $2$-nd day, he will pay $4$ yen on the $1$-st day and $6$ yen on the $2$-nd day, for a total of $10$ yen.
It is impossible to make the total payment less than $10$ yen, so we should print $10$.


Sample Input 2

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

Sample Output 2

163089627821228

It is optimal to do without Snuke Prime.


Sample Input 3

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

Sample Output 3

88206004785464

Input

题意翻译

Snuke 开了一家公司,提供各种各样的服务。并且公司推出了一个称作 Snuke Prime 的会员方案。 在每天的开始,用户可以支付 $C$ 元,购买一天会员资格。拥有会员资格的期间,可以自由使用公司提供的所有服务。 高桥君想要使用这个公司的 $N$ 种服务。使用第i种服务的期间是从第 $a_{i}$ 天的开始到第 $b_{i}$ 天的结束。在没有会员资格的期间,要使用第 $i$ 种服务,每天需要支付 $c_{i}$ 元。 求出高桥君需要支付的最小合计金额。 第一行输入两个整数 $N$ 和 $C$。从第 $2$ 行到第 $N$ 行,每行三个整数 $a_{i}$,$b_{i}$,$c_{i}$。 Translated by @[xibaohe](https://www.luogu.com.cn/user/601747)

加入题单

上一题 下一题 算法标签: