A15825. 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.

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.

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.