$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$ |
適切な小課題の依存関係が有効になっています。