G. Gamer's Karma Farming Strat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After spending a long time collecting data and training his AI, Daeng confidently predicts that his mom will assign him $$$N$$$ household tasks to complete during the day.

Task $$$i$$$ is scheduled to take place during a specific time interval, starting at second $$$l_i$$$ and ending at second $$$r_i$$$ (inclusive). The task also has a karma value $$$k_i$$$. It is guaranteed that no two task intervals overlap with each other.

At the start of the day, Daeng's karma score is $$$0$$$. When the clock reaches the start time $$$l_i$$$ of a task, Daeng must make a choice:

  • Do the task: Daeng gains $$$k_i$$$ karma points. However, from the second $$$l_i$$$ to $$$r_i$$$, he is fully occupied and cannot do anything else.
  • Skip the task: Daeng may choose to ignore the task, but this is only allowed if his current karma score is at least $$$k_i$$$. In that case, his karma score decreases by $$$k_i$$$.

In addition to household tasks, Daeng wants to enjoy his favorite game as many times as possible throughout the day. Each game session lasts exactly $$$M$$$ seconds. While Daeng is playing, he cannot work on tasks and must be continuous once started. Also, he can only have one gaming session at a time.

Time during the day is measured from second $$$0$$$ up to second $$$86{,}399$$$, making exactly one full day. Since each task interval includes both its starting and ending seconds, if a task ends at time $$$r$$$, Daeng is free to begin another activity at time $$$r+1$$$. For example, if a game begins at second $$$0$$$, it will finish at second $$$M-1$$$.

Find the maximum number of game sessions Daeng can have on the day.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10{,}000$$$, $$$1 \leq M \leq 86{,}400$$$) — the number of tasks and the duration of one game session in seconds.

Each of the next $$$N$$$ lines contains three integers $$$l_i,\; r_i,\; k_i$$$ ($$$0 \leq l_i \leq r_i \lt 86{,}400$$$, $$$1 \leq k_i \leq 20{,}000$$$) — the start time, end time, and karma value of the $$$i$$$-th task.

It is guaranteed that no task intervals overlap. That is, for any integer $$$i$$$ and $$$j$$$ between $$$1$$$ to $$$N$$$, if $$$i \neq j$$$, then $$$min(r_i, r_j) \lt max(l_i, l_j)$$$.

Also, $$$\sum_{i=1}^{N} k_i \leq 20{,}000$$$.

Output

Print a single integer — the maximum number of game sessions Daeng can play during the day without violating the rules.

Examples
Input
3 1
0 1 1
2 4 1
6 10 1
Output
86395
Input
10 7
1 2 2
3 7 1
10 11 3
12 13 3
15 16 3
18 21 5
23 23 1
24 25 5
26 30 5
31 33 2
Output
12341
Note

Sample explanation

In the first example, Daeng must do task 1 since he initially has no karma points. Then he can choose whether or not to do task 2. The optimal choice is to do task 2 and skip task 3.