There are $n$ tasks. Task $i$ needs to occupy one cell in $[l_i,r_i]$. If the index of the occupied cell is $\le t_i$, an extra reward of $1$ is obtained. Find the maximum reward that can be obtained given that all tasks are completed.
Input
The first line contains two integers $n,m$, representing the number of tasks and the number of cells, respectively.
The next $n$ lines each contain three integers $l,r,t$, representing a task.
Output
If it is impossible to complete all tasks, output $-1$; otherwise, output the answer.
Examples
Input 1
3 3 1 2 1 1 2 1 2 3 2
Output 1
1
Note
By assigning the tasks to cells $1,2,3$ in order, one task receives the reward.
Constraints
For all test data, it holds that $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Subtask | Score | Additional Constraints |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | All $l_i$ are equal |
| $3$ | $3$ | All $t_i$ are equal |
| $4$ | $19$ | $n,m \le 500$ |
| $5$ | $20$ | $n,m \le 2000$ |
| $6$ | $21$ | $n,m \le 10^5$ |
| $7$ | $22$ | $n,m \le 5\times 10^5$ |
Reasonable subtask dependencies are enabled.