Có $n$ nhiệm vụ, nhiệm vụ $i$ cần chiếm một ô trong đoạn $[l_i,r_i]$. Nếu chỉ số của ô bị chiếm $\le t_i$ thì nhận thêm phần thưởng là $1$. Hãy tìm phần thưởng lớn nhất có thể đạt được khi hoàn thành tất cả các nhiệm vụ.
Dữ liệu vào
Một dòng gồm hai số nguyên $n,m$, lần lượt là số lượng nhiệm vụ và số lượng ô.
Tiếp theo là $n$ dòng, mỗi dòng gồm ba số nguyên $l,r,t$ biểu thị một nhiệm vụ.
Dữ liệu ra
Nếu không thể hoàn thành tất cả các nhiệm vụ, hãy in ra $-1$, ngược lại in ra đáp án.
Ví dụ
Dữ liệu vào 1
3 3 1 2 1 1 2 1 2 3 2
Dữ liệu ra 1
1
Ghi chú
Phân bổ các nhiệm vụ lần lượt vào các ô $1,2,3$, ta thấy có một nhiệm vụ nhận được phần thưởng.
Giới hạn
Với mọi dữ liệu, thỏa mãn $1\le n,m\le 5\times 10^5, 1\le l_i \le t_i \le r_i \le m$.
| Nhiệm vụ con | Điểm | Giới hạn đặc biệt |
|---|---|---|
| $1$ | $3$ | $n,m \le 15$ |
| $2$ | $12$ | Tất cả $l_i$ bằng nhau |
| $3$ | $3$ | Tất cả $t_i$ bằng nhau |
| $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$ |
Đã bật phụ thuộc nhiệm vụ con hợp lý.