Hay $n$ tareas. La tarea $i$ necesita ocupar una celda en $[l_i,r_i]$. Si el índice de la celda ocupada es $\le t_i$, se obtiene una recompensa adicional de $1$. Halla la máxima recompensa que se puede obtener bajo la condición de que se completen todas las tareas.
Entrada
Una línea con dos enteros $n,m$, que representan la cantidad de tareas y la cantidad de celdas, respectivamente.
Las siguientes $n$ líneas contienen tres enteros $l,r,t$ por línea, que representan una tarea.
Salida
Si es imposible completar todas las tareas, imprime $-1$; de lo contrario, imprime la respuesta.
Ejemplos
Entrada 1
3 3 1 2 1 1 2 1 2 3 2
Salida 1
1
Nota
Al asignar las tareas en orden a las celdas $1,2,3$, se observa que una tarea obtiene recompensa.
Restricciones
Para todos los datos, se cumple $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Subtarea | Puntuación | Restricciones especiales |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Todos los $l_i$ son iguales |
| $3$ | $3$ | Todos los $t_i$ son iguales |
| $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$ |
Se han activado dependencias razonables entre subtareas.