Il y a $n$ tâches. La tâche $i$ doit occuper une case dans $[l_i,r_i]$. Si le numéro de la case occupée est $\le t_i$, elle rapporte une récompense supplémentaire de $1$. Déterminez la récompense maximale qu'il est possible d'obtenir en accomplissant toutes les tâches.
Entrée
Une ligne contenant deux entiers $n,m$, représentant respectivement le nombre de tâches et le nombre de cases.
Les $n$ lignes suivantes contiennent chacune trois entiers $l,r,t$ décrivant une tâche.
Sortie
S'il est impossible d'accomplir toutes les tâches, affichez $-1$ ; sinon, affichez la réponse.
Exemples
Entrée 1
3 3 1 2 1 1 2 1 2 3 2
Sortie 1
1
Remarque
En attribuant les tâches dans l'ordre aux cases $1,2,3$, on constate qu'une tâche obtient une récompense.
Contraintes
Pour toutes les données, $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Sous-tâche | Points | Contraintes particulières |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Tous les $l_i$ sont égaux |
| $3$ | $3$ | Tous les $t_i$ sont égaux |
| $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$ |
Des dépendances raisonnables entre les sous-tâches sont activées.