Terdapat $n$ tugas. Tugas $i$ harus menempati satu petak di dalam rentang $[l_i,r_i]$. Jika nomor petak yang ditempati $\le t_i$, maka akan diperoleh hadiah tambahan sebesar $1$. Carilah hadiah maksimum yang dapat diperoleh dengan syarat semua tugas selesai dikerjakan.
Masukan
Satu baris berisi dua bilangan bulat $n,m$, masing-masing menyatakan banyaknya tugas dan banyaknya petak.
Berikutnya terdapat $n$ baris, masing-masing berisi tiga bilangan bulat $l,r,t$ yang menyatakan sebuah tugas.
Keluaran
Jika tidak mungkin menyelesaikan semua tugas, keluarkan $-1$; jika mungkin, keluarkan jawabannya.
Contoh
Masukan 1
3 3 1 2 1 1 2 1 2 3 2
Keluaran 1
1
Catatan
Dengan menempatkan tugas secara berurutan ke petak $1,2,3$, terlihat bahwa ada satu tugas yang memperoleh hadiah.
Batasan
Untuk semua data uji, berlaku $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Subsoal | Poin | Batasan Khusus |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Semua $l_i$ bernilai sama |
| $3$ | $3$ | Semua $t_i$ bernilai sama |
| $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$ |
Ketergantungan subsoal yang wajar telah diaktifkan.