Det finns $n$ uppgifter. Uppgift $i$ behöver uppta en ruta i intervallet $[l_i,r_i]$. Om numret på den upptagna rutan är $\le t_i$ får man en extra belöning på $1$. Bestäm den maximala belöningen som kan erhållas under villkoret att alla uppgifter slutförs.
Indata
En rad med två heltal $n,m$, som anger antalet uppgifter respektive antalet rutor.
Därefter följer $n$ rader, där varje rad innehåller tre heltal $l,r,t$ som beskriver en uppgift.
Utdata
Om det är omöjligt att slutföra alla uppgifter, skriv ut $-1$, annars skriv ut svaret.
Exempel
Indata 1
3 3 1 2 1 1 2 1 2 3 2
Utdata 1
1
Förklaring
Genom att tilldela uppgifterna i ordning till rutorna $1,2,3$ ser man att en uppgift får belöning.
Begränsningar
För all testdata gäller $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Deluppgift | Poäng | Särskilda begränsningar |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Alla $l_i$ är lika |
| $3$ | $3$ | Alla $t_i$ är lika |
| $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$ |
Rimliga beroenden mellan deluppgifter är aktiverade.