$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$ |
합리적인 서브태스크 의존성이 적용되어 있습니다.