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.

If $$$m = 0$$$, i. e. there are no users trying to transmit data during this millisecond, nothing happens.
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$$$.
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.

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.

Flow Control

Examples