Moovie Mooving (Gold)

Có $N$ bộ phim và thời gian cần lấp đầy là $L$ phút. Mỗi bộ phim $i$ có thời lượng $D_i$ phút và $C_i$ suất chiếu, mỗi suất bắt đầu vào một thời điểm cho trước. Bessie bắt đầu ở thời điểm $0$ và muốn theo dõi phim liên tục đến thời điểm $L$.

Quy tắc: khi Bessie đang ở thời điểm $t$, cô có thể "nhảy vào" bộ phim $i$ đang chiếu nếu có suất chiếu $s\le t$ với $s+D_i>t$ (tức là bộ phim đang phát và chưa kết thúc). Sau đó cô xem đến hết suất đó, kết thúc ở thời điểm $s+D_i$. Mỗi bộ phim chỉ được dùng một lần.

Tìm số bộ phim tối thiểu để Bessie xem từ thời điểm $0$ đến ít nhất thời điểm $L$, hoặc in $-1$ nếu không thể.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $L$.

• $N$ dòng tiếp theo, mỗi dòng mô tả một bộ phim: $D_i$ (thời lượng), $C_i$ (số suất chiếu), rồi $C_i$ thời điểm bắt đầu tăng dần.

Dữ liệu ra

Số nguyên là số bộ phim tối thiểu, hoặc $-1$.

Ràng buộc

• $1\le N\le 20$
• $1\le L\le {10}^8$
• $1\le D_i\le L$
• $1\le C_i\le 1000$
• Các thời điểm chiếu nằm trong đoạn $[0,L]$

Ví dụ