Є $n$ завдань. Завданню $i$ потрібно зайняти одну клітинку з відрізка $[l_i,r_i]$. Якщо номер зайнятої клітинки $\le t_i$, то додатково надається винагорода $1$. Знайдіть максимальну винагороду, яку можна отримати за умови виконання всіх завдань.
Вхідні дані
У першому рядку задано два цілі числа $n,m$ — кількість завдань і кількість клітинок відповідно.
У наступних $n$ рядках задано по три цілі числа $l,r,t$, що описують одне завдання.
Вихідні дані
Якщо неможливо виконати всі завдання, виведіть $-1$, інакше виведіть відповідь.
Приклади
Вхідні дані 1
3 3 1 2 1 1 2 1 2 3 2
Вихідні дані 1
1
Примітка
Якщо послідовно призначити завдання клітинкам $1,2,3$, то одне завдання отримає винагороду.
Обмеження
Для всіх даних виконується $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Підзадача | Бали | Додаткові обмеження |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Усі $l_i$ рівні |
| $3$ | $3$ | Усі $t_i$ рівні |
| $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$ |
Увімкнено розумні залежності між підзадачами.