Danych jest $n$ zadań. Zadanie $i$ musi zająć jedno pole z przedziału $[l_i,r_i]$. Jeśli numer zajętego pola spełnia $\le t_i$, to dodatkowo otrzymujemy nagrodę równą $1$. Wyznacz maksymalną nagrodę, jaką można uzyskać pod warunkiem wykonania wszystkich zadań.
Wejście
W pierwszym wierszu znajdują się dwie liczby całkowite $n,m$, oznaczające odpowiednio liczbę zadań oraz liczbę pól.
W kolejnych $n$ wierszach znajdują się po trzy liczby całkowite $l,r,t$ opisujące pojedyncze zadanie.
Wyjście
Jeśli nie da się wykonać wszystkich zadań, wypisz $-1$; w przeciwnym razie wypisz odpowiedź.
Przykład
Wejście 1
3 3 1 2 1 1 2 1 2 3 2
Wyjście 1
1
Uwagi
Przypisując zadania kolejno do pól $1,2,3$, widzimy, że jedno zadanie otrzymuje nagrodę.
Ograniczenia
Dla wszystkich danych zachodzi $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Podzadanie | Punkty | Dodatkowe ograniczenia |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Wszystkie $l_i$ są równe |
| $3$ | $3$ | Wszystkie $t_i$ są równe |
| $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$ |
Włączono rozsądne zależności między podzadaniami.