Flow Control

在一个带宽为 $b$ 字节每毫秒的网络中，有 $n$ 个用户需要传输数据。 第 $i$ 个用户会在第 $s_i$ 毫秒到第 $t_i$ 毫秒（包含端点）使用该网络，其初始传输速度为 $d_i$。也就是说，这名用户在 $s_i$ 毫秒开始使用该网络，此时其传输速度为 $d_i$。随后传输速度会遵循以下程序而改变。 假设在第 $x$ 毫秒有 $m$ 个用户使用该网络，第 $i$ 个用户当前的传输速度为 $t_i \ge 0$。 1. 若 $m = 0$，此时没有用户在使用网络。什么都不会发生。 2. 如果所有 $t_i$ 的和 $\le b$，每个使用网络的用户都能成功传输数据（第 $i$ 个用户传输了 $t_i$ 字节）。在这之后，每个用户的传输速度（即每个 $t_i$）都会增加 $1$。 3. 如果所有 $t_i$ 的和 $> b$，会发生网络拥塞。没有用户在该毫秒内能传输数据。在这之后，每个用户的传输速度都会除以二（即每个 $t_i$ 被替换为 $\left\lfloor \frac{t_i}{2}\right\rfloor$）。 给定 $n, b$ 和每个 $s_i, t_i, d_i$，请计算所有用户总共可以传输的数据量。 $1\le n\le 2\times 10^5, \ 1\le b, d_i \le 10^9, \ 1\le s_i\le t_i\le 10^9$。

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.

1 3
1 5 2

10

1 10
7 11 1000

0

2 6
1 12 1
8 20 3

64

3 10
1 100 1
30 60 20
40 80 6

534

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.