Det finnes $n$ oppgaver. Oppgave $i$ må oppta én rute i intervallet $[l_i,r_i]$. Hvis nummeret på den opptatte ruten er $\le t_i$, får man en ekstra belønning på $1$. Finn den maksimale belønningen man kan oppnå gitt at alle oppgavene fullføres.
Inndata
Én linje med to heltall $n,m$, som angir henholdsvis antall oppgaver og antall ruter.
Deretter følger $n$ linjer, hver med tre heltall $l,r,t$ som beskriver en oppgave.
Utdata
Hvis det er umulig å fullføre alle oppgavene, skriv ut $-1$, ellers skriv ut svaret.
Eksempler
Inndata 1
3 3 1 2 1 1 2 1 2 3 2
Utdata 1
1
Forklaring
Ved å tildele oppgavene i rekkefølge til rutene $1,2,3$, ser man at én oppgave får belønning.
Begrensninger
For alle testdata gjelder $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Deloppgave | Poeng | Spesielle begrensninger |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Alle $l_i$ er like |
| $3$ | $3$ | Alle $t_i$ er like |
| $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$ |
Rimelige avhengigheter mellom deloppgavene er aktivert.