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.