CF1804G.Flow Control

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.

拉吉拥有一条连接其办公室与互联网的物理网络线路。该线路的带宽为 $b$ 字节/毫秒。

共有 $n$ 个用户希望使用该网络线路传输数据。其中第 $i$ 个用户将在毫秒 $s_i$ 至毫秒 $f_i$（含端点）期间使用该线路。其初始数据速率为 $d_i$，即：在毫秒 $s_i$ 时，其数据速率被设为 $d_i$；此后，该速率将按如下所述规则变化。

流量控制过程如下：假设在毫秒 $x$ 期间，有 $m$ 个用户试图通过该网络线路传输数据。记这 $m$ 个用户在该毫秒开始时的数据速率分别为 $t_i$（$i = 1, 2, \dots, m$）。所有 $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$。

拉吉已知所有参数 $n$、$b$、$s_i$、$f_i$ 和 $d_i$，他希望计算所有用户传输的字节总数。

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.

输入的第一行包含两个整数 $n$ 和 $b$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq b \leq 10^9$），分别表示将使用该线路的用户数量和线路带宽。

接下来的 $n$ 行中，每行包含三个整数 $s_i$、$f_i$ 和 $d_i$（$1 \leq s_i \leq f_i \leq 10^9$，$1 \leq d_i \leq 10^9$），表示第 $i$ 个用户将在每个介于 $s_i$ 与 $f_i$（含端点）之间的毫秒时刻尝试传输数据，且第 $i$ 个用户的初始数据传输速率为 $d_i$。

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

输出一个整数——所有用户成功传输的字节数总和。

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.

考虑第一个例子。

• 第 1 毫秒：用户 $1$ 传输 $2$ 字节。
• 第 2 毫秒：用户 $1$ 传输 $3$ 字节。
• 第 3 毫秒：发生拥塞，无用户传输数据。
• 第 4 毫秒：用户 $1$ 传输 $2$ 字节。
• 第 5 毫秒：用户 $1$ 传输 $3$ 字节。

在第二个例子中，从第 $7$ 毫秒到第 $11$ 毫秒（含）的每一毫秒均发生拥塞，且唯一用户将其传输速率降低了两次。然而，在断开连接前，其降速幅度仍不足。

考虑第三个例子。

• 第 1 毫秒：用户 $1$ 传输 $1$ 字节。
• 第 2 毫秒：用户 $1$ 传输 $2$ 字节。
• 第 3 毫秒：用户 $1$ 传输 $3$ 字节。
• 第 4 毫秒：用户 $1$ 传输 $4$ 字节。
• 第 5 毫秒：用户 $1$ 传输 $5$ 字节。
• 第 6 毫秒：用户 $1$ 传输 $6$ 字节。
• 第 7 毫秒：发生拥塞，无用户传输数据。
• 第 8 毫秒：用户 $1$ 传输 $3$ 字节，用户 $2$ 传输 $3$ 字节。
• 第 9 毫秒：发生拥塞，无用户传输数据。
• 第 10 毫秒：用户 $1$ 传输 $2$ 字节，用户 $2$ 传输 $2$ 字节。
• 第 11 毫秒：用户 $1$ 传输 $3$ 字节，用户 $2$ 传输 $3$ 字节。
• 第 12 毫秒：发生拥塞，无用户传输数据。
• 第 13 毫秒：用户 $2$ 传输 $2$ 字节。
• 第 14 毫秒：用户 $2$ 传输 $3$ 字节。
• 第 15 毫秒：用户 $2$ 传输 $4$ 字节。
• 第 16 毫秒：用户 $2$ 传输 $5$ 字节。
• 第 17 毫秒：用户 $2$ 传输 $6$ 字节。
• 第 18 毫秒：发生拥塞，无用户传输数据。
• 第 19 毫秒：用户 $2$ 传输 $3$ 字节。
• 第 20 毫秒：用户 $2$ 传输 $4$ 字节。