Es gibt $n$ Aufgaben. Aufgabe $i$ muss ein Feld im Bereich $[l_i,r_i]$ belegen. Wenn die Nummer des belegten Feldes $\le t_i$ ist, erhält man zusätzlich eine Belohnung von $1$. Bestimme die maximale Belohnung, die unter der Bedingung erreicht werden kann, dass alle Aufgaben erledigt werden.
Eingabe
Eine Zeile mit zwei ganzen Zahlen $n,m$, die die Anzahl der Aufgaben bzw. die Anzahl der Felder angeben.
In den nächsten $n$ Zeilen stehen jeweils drei ganze Zahlen $l,r,t$, die eine Aufgabe beschreiben.
Ausgabe
Falls es unmöglich ist, alle Aufgaben zu erledigen, gib $-1$ aus, andernfalls gib die Antwort aus.
Beispiele
Eingabe 1
3 3 1 2 1 1 2 1 2 3 2
Ausgabe 1
1
Hinweis
Wenn man die Aufgaben der Reihe nach den Feldern $1,2,3$ zuweist, erhält genau eine Aufgabe eine Belohnung.
Beschränkungen
Für alle Testdaten gilt $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Teilaufgabe | Punkte | Zusätzliche Beschränkungen |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Alle $l_i$ sind gleich |
| $3$ | $3$ | Alle $t_i$ sind gleich |
| $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$ |
Sinnvolle Abhängigkeiten zwischen den Teilaufgaben sind aktiviert.