Есть $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$ |
Включены разумные зависимости между подзадачами.