Ci sono $n$ compiti. Il compito $i$ deve occupare una casella nell'intervallo $[l_i,r_i]$. Se l'indice della casella occupata è $\le t_i$, si ottiene una ricompensa aggiuntiva pari a $1$. Trova la ricompensa massima ottenibile a condizione che tutti i compiti vengano completati.
Input
Una riga contenente due interi $n,m$, rispettivamente il numero di compiti e il numero di caselle.
Seguono $n$ righe, ciascuna con tre interi $l,r,t$ che rappresentano un compito.
Output
Se non è possibile completare tutti i compiti, stampa $-1$; altrimenti stampa la risposta.
Examples
Input 1
3 3 1 2 1 1 2 1 2 3 2
Output 1
1
Note
Assegnando i compiti nell'ordine alle caselle $1,2,3$, si vede che un compito ottiene la ricompensa.
Constraints
Per tutti i dati, vale $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Subtask | Punteggio | Limitazioni speciali |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Tutti gli $l_i$ sono uguali |
| $3$ | $3$ | Tutti i $t_i$ sono uguali |
| $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$ |
Sono attivate ragionevoli dipendenze tra i subtask.