310248: CF1804G. Flow Control

G. Flow Controltime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Raj has a single physical network line that connects his office to the Internet. This line bandwidth is $b$ bytes per millisecond.

There are $n$ users who would like to use this network line to transmit some data. The $i$-th of them will use the line from millisecond $s_i$ to millisecond $f_i$ inclusive. His initial data rate will be set to $d_i$. That means he will use data rate equal to $d_i$ for millisecond $s_i$, and then it will change according to the procedure described below.

The flow control will happen as follows. Suppose there are $m$ users trying to transmit some data via the given network line during millisecond $x$. Denote as $t_i$ the data rate that the $i$-th of these $m$ users has at the beginning of this millisecond. All $t_i$ are non-negative integer values.

1. If $m = 0$, i. e. there are no users trying to transmit data during this millisecond, nothing happens.
2. If the sum of all $t_i$ is less than or equal to $b$, each active user successfully completes his transmission (the $i$-th active user transmits $t_i$ bytes). After that, the data rate of each active user grows by $1$, i. e. each $t_i$ is increased by $1$.
3. If the sum of all $t_i$ is greater than $b$, the congestion occurs and no data transmissions succeed this millisecond at all. If that happens, each $t_i$ decreases twice, i. e. each $t_i$ is replaced with $\lfloor \frac{t_i}{2} \rfloor$.

Raj knows all the values $n$, $b$, $s_i$, $f_i$, and $d_i$, he wants to calculate the total number of bytes transmitted by all the users in the aggregate.

Input

The first line of the input contains two integers $n$ and $b$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq b \leq 10^9$), the number of users who will use the line and the line bandwidth, respectively.

Each of the following $n$ lines contains three integers $s_i$, $f_i$ and $d_i$ ($1 \leq s_i \leq f_i \leq 10^9$, $1 \leq d_i \leq 10^9$), denoting that the $i$-th user will try to transmit data during each millisecond between $s_i$ and $f_i$ inclusive, and the initial data rate of the $i$-th user.

Output

Print one integer — the total number of bytes all users will successfully transmit.

ExamplesInput

1 3
1 5 2

Output

10

Input

1 10
7 11 1000

Output

0

Input

2 6
1 12 1
8 20 3

Output

64

Input

3 10
1 100 1
30 60 20
40 80 6

Output

534

Note

Consider the first example.

• Millisecond $1$: User $1$ transmits $2$ bytes.
• Millisecond $2$: User $1$ transmits $3$ bytes.
• Millisecond $3$: Congestion occurs, and no user transmits data.
• Millisecond $4$: User $1$ transmits $2$ bytes.
• Millisecond $5$: User $1$ transmits $3$ bytes.

In the second example, at each millisecond from the $7$-th to the $11$-th inclusive, congestion occurs, and the only user decreases their rate twice. However, they don't decrease the speed enough before disconnecting.

Consider the third example.

• Millisecond $1$: User $1$ transmits $1$ bytes.
• Millisecond $2$: User $1$ transmits $2$ bytes.
• Millisecond $3$: User $1$ transmits $3$ bytes.
• Millisecond $4$: User $1$ transmits $4$ bytes.
• Millisecond $5$: User $1$ transmits $5$ bytes.
• Millisecond $6$: User $1$ transmits $6$ bytes.
• Millisecond $7$: Congestion occurs, and no user transmits data.
• Millisecond $8$: User $1$ transmits $3$ bytes. User $2$ transmits $3$ bytes.
• Millisecond $9$: Congestion occurs, and no user transmits data.
• Millisecond $10$: User $1$ transmits $2$ bytes. User $2$ transmits $2$ bytes.
• Millisecond $11$: User $1$ transmits $3$ bytes. User $2$ transmits $3$ bytes.
• Millisecond $12$: Congestion occurs, and no user transmits data.
• Millisecond $13$: User $2$ transmits $2$ bytes.
• Millisecond $14$: User $2$ transmits $3$ bytes.
• Millisecond $15$: User $2$ transmits $4$ bytes.
• Millisecond $16$: User $2$ transmits $5$ bytes.
• Millisecond $17$: User $2$ transmits $6$ bytes.
• Millisecond $18$: Congestion occurs, and no user transmits data.
• Millisecond $19$: User $2$ transmits $3$ bytes.
• Millisecond $20$: User $2$ transmits $4$ bytes.

题目大意：
Raj有一条物理网络线路连接他的办公室和互联网，这条线路的带宽是每毫秒b字节。有n个用户想要使用这条线路传输数据。第i个用户将从毫秒s_i到f_i（包括f_i）使用线路，他的初始数据传输率将被设置为d_i。这意味着他在s_i毫秒时将使用d_i的数据传输率，然后根据下面描述的过程进行变化。

流量控制将按以下方式发生。假设在x毫秒内有m个用户尝试通过网络线路传输数据。用t_i表示这m个用户中的第i个用户在该毫秒开始时的数据传输率。所有t_i都是非负整数值。
1. 如果m=0，即在这个毫秒内没有用户尝试传输数据，那么什么也不会发生。
2. 如果所有t_i的总和小于或等于b，则每个活动用户成功完成他们的传输（第i个活动用户传输t_i字节）。之后，每个活动用户的数据传输率增加1，即每个t_i增加1。
3. 如果所有t_i的总和大于b，则发生拥塞，并且在这个毫秒内没有数据传输成功。如果发生这种情况，每个t_i减少两倍，即每个t_i被替换为$$\lfloor \frac{t_i}{2} \rfloor$$。

Raj知道所有的值n、b、s_i、f_i和d_i，他想要计算所有用户总共成功传输的字节数。

输入输出数据格式：
输入：
第一行包含两个整数n和b（1≤n≤2×10^5，1≤b≤10^9），分别是将使用线路的用户数量和线路带宽。
接下来的n行，每行包含三个整数s_i、f_i和d_i（1≤s_i≤f_i≤10^9，1≤d_i≤10^9），表示第i个用户将在s_i到f_i（包括f_i）的每个毫秒尝试传输数据，以及第i个用户的初始数据传输率。

输出：
打印一个整数——所有用户将成功传输的总字节数。题目大意： Raj有一条物理网络线路连接他的办公室和互联网，这条线路的带宽是每毫秒b字节。有n个用户想要使用这条线路传输数据。第i个用户将从毫秒s_i到f_i（包括f_i）使用线路，他的初始数据传输率将被设置为d_i。这意味着他在s_i毫秒时将使用d_i的数据传输率，然后根据下面描述的过程进行变化。 流量控制将按以下方式发生。假设在x毫秒内有m个用户尝试通过网络线路传输数据。用t_i表示这m个用户中的第i个用户在该毫秒开始时的数据传输率。所有t_i都是非负整数值。 1. 如果m=0，即在这个毫秒内没有用户尝试传输数据，那么什么也不会发生。 2. 如果所有t_i的总和小于或等于b，则每个活动用户成功完成他们的传输（第i个活动用户传输t_i字节）。之后，每个活动用户的数据传输率增加1，即每个t_i增加1。 3. 如果所有t_i的总和大于b，则发生拥塞，并且在这个毫秒内没有数据传输成功。如果发生这种情况，每个t_i减少两倍，即每个t_i被替换为$$\lfloor \frac{t_i}{2} \rfloor$$。 Raj知道所有的值n、b、s_i、f_i和d_i，他想要计算所有用户总共成功传输的字节数。 输入输出数据格式： 输入： 第一行包含两个整数n和b（1≤n≤2×10^5，1≤b≤10^9），分别是将使用线路的用户数量和线路带宽。 接下来的n行，每行包含三个整数s_i、f_i和d_i（1≤s_i≤f_i≤10^9，1≤d_i≤10^9），表示第i个用户将在s_i到f_i（包括f_i）的每个毫秒尝试传输数据，以及第i个用户的初始数据传输率。 输出： 打印一个整数——所有用户将成功传输的总字节数。