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