You are a great mage, and you are now facing $n$ monsters. The appearance time of the $i$-th monster is $[l_i, r_i)$, and it has experience value $w_i$. For monster $i$, you may choose a real number $k_i \in [l_i, r_i]$, and cast a sealing spell to control this monster during the time interval $[l_i, k_i)$. In particular, if $k_i = l_i$, it means that you do not cast a sealing spell on this monster. Since humans have limits, at any moment, you can cast spells on at most $K$ monsters simultaneously, where $K$ is a given constant.

You have a proficiency value $W$. Since you have not used sealing spells for a long time, at time $0$ we have $W = 0$. For monster $i$, if $k_i = r_i$, then the monster is successfully sealed, and at time $r_i$ your proficiency increases by $w_i$; if $k_i < r_i$, then the monster will attack you at time $k_i$, causing your proficiency to be reset to $0$.

At any moment, you may choose to cast an ultimate secret art, turning all $n$ monsters on the timeline into $W$ coins, and leave with them. If multiple events occur at the same time (proficiency increase, proficiency reset, ultimate secret art), their order of effect can be arranged arbitrarily.

Now, determine the maximum number of coins you can take away.

Input

The first line contains two positive integers $n, K$.

The next $n$ lines each contain three positive integers $l_i, r_i, w_i$, describing one monster.

Output

Output one line containing a single integer, the answer.

Example

Example Input 1

3 1
1 3 1
2 5 1
4 6 1

Example Output 1

2

Example Input 2

10 2
4 10 14
2 17 87
5 12 84
6 11 71
1 13 62
8 9 55
7 14 6
15 20 87
3 19 18
16 18 96

Example Output 2

338

Example 3

See the additional files ex_seal3.in/ans. This example satisfies the constraints of Subtasks 5 and 6.

Example Explanation

For Example 1, choose $k_1 = 3, k_2 = 2, k_3 = 6$. Then at time $2$, $W$ is reset to $0$; at time $3$, $W$ increases by $1$; at time $6$, $W$ increases by $1$. At this point, you can obtain $2$ coins. It is easy to see that obtaining $3$ coins is impossible.

Constraints

For all data, $n, l_i, r_i, w_i, K$ are positive integers, $1 \le K \le n \le 3 \times 10^5$, $1 \le w_i \le 10^9$, $1 \le l_i < r_i \le 2n$, and it is guaranteed that $l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n$ form a permutation of $1 \sim 2n$.

The special constraints and scores of each subtask are as follows: