Safe Crossings

You are faced with the challenge of crossing a road with $M$ lanes. The road is busy, and across all lanes there are only $N$ gaps in the traffic through which you may cross, each having a start and end time at your location (which you know thanks to cameras you set up down the road).

Specifically, a gap in lane $l$ has a start and end time $s$ and $e$. This indicates that at times $s,s+1,s+2,\ldots,e-2,e-1$ there is a gap in traffic in this lane, and it is safe to be in this lane. Note that it is not safe to be in this lane exactly at the end time $e$.

You start at time $0$, in front of lane $1$, and in each second you may either move forward to the next lane (arriving in the next unit of time), or wait. You may only occupy a lane during a gap in that lane, and you may not move backwards or along the lanes. (Note that it is possible to move between lanes when the current gap ends at the same time the gap in the next lane begins).

What you are interested in is how safely you can cross. Specifically, if your safety at each moment during your crossing is the number of units of time before the gap you are in ends, then the overall safety is the minimum of the safety scores for each moment. If it is not possible to get across, the safety is $0$.

Please note: If you are receiving 'Time Limit Exceeded' with Python code, you may need to submit with language 'Python 3.6 (PyPy 7.3)'

Input

The first line will contain two space-seperated integers, $N$ and $M$.

There then follow $N$ lines, the $i^{th}$ of which contain three space-seperated integers, $l_i$, $s_i$ and $e_i$, which denotes that on lane $l_i$, there will be a gap in the traffic from time $s_i$ up to but not including time $e_i$.

Note that there will be no guaranteed order to the gaps.

Output

Output the maximum safety score you can acheive while crossing the road ($0$ if crossing is not possible).

Constraints

• $1 \le N \le 100,000$
• $1 \le M \le 100,000$
• Every lane has at least one gap.
• $1 \le l_i \le M$ and $0 \le s_i \lt e_i \le 100,000,000$ for all $0 \le i \lt N$.
• Gaps in the same lane will not intersect or overlap, i.e. if $l_i = l_j$ and $i \neq j$ then $s_i \neq s_j$ and if $s_i \lt s_j$ then $e_i \lt s_j$.

Subtasks

• Subtask 1 (10%): $M = 1$, i.e. there is only one lane.
• Subtask 2 (20%): Each lane has only one gap.
• Subtask 3 (20%): $N \le 1000$ and $e_i - s_i \le 100$ for all $0 \le i \lt N$.
• Subtask 4 (20%): $N \le 1000$.
• Subtask 5 (30%): No further constraints.

Sample 1 Explanation

In one route across you could wait until time 2, then cross into lane 1, arriving at time 3. You then wait until time 6, then cross into lane 2, arriving at time 7, and then exit the road. The safety score for this route is $min(9-6, 12-7) = 3$, which is the maximum possible.