On $n$ tehtävää. Tehtävän $i$ täytyy varata yksi ruutu väliltä $[l_i,r_i]$. Jos varatun ruudun numero on $\le t_i$, saadaan $1$ lisäpalkinto. Etsi suurin mahdollinen palkinto, joka voidaan saavuttaa, kun kaikki tehtävät suoritetaan.
Syöte
Yhdellä rivillä on kaksi kokonaislukua $n,m$, jotka ilmoittavat tehtävien lukumäärän ja ruutujen lukumäärän.
Seuraavilla $n$ rivillä on kullakin kolme kokonaislukua $l,r,t$, jotka kuvaavat yhden tehtävän.
Tuloste
Jos kaikkia tehtäviä ei ole mahdollista suorittaa, tulosta $-1$, muuten tulosta vastaus.
Esimerkit
Syöte 1
3 3 1 2 1 1 2 1 2 3 2
Tuloste 1
1
Selitys
Kun tehtävät sijoitetaan järjestyksessä ruutuihin $1,2,3$, nähdään, että yksi tehtävä saa palkinnon.
Rajoitukset
Kaikissa syötteissä pätee $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Osatehtävä | Pisteet | Erityisrajoitukset |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Kaikki $l_i$ ovat yhtä suuria |
| $3$ | $3$ | Kaikki $t_i$ ovat yhtä suuria |
| $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$ |
Kohtuulliset osatehtävien riippuvuudet ovat käytössä.