Giữ hiệu ứng
An đang chơi Minecraft. Cậu đã xây được một số lượng hải đăng nhất định. Cậu đang muốn sử dụng hiệu ứng từ các ngọn hải đăng liên tục trong $L$ phút.
Cậu đã xây tất cả $N$ ngọn hải đăng. Mỗi ngọn hải đăng có thể cung cấp một loại hiệu ứng có hiệu lực trong $D_i$ phút. Nhưng chỉ có $M_i$ thời điểm hiệu ứng được kích hoạt $T_{i,j}$. Tại thời điểm một hiệu ứng đang được kích hoạt, nếu cậu muốn sử dụng hiệu ứng, cần xóa bỏ hiệu ứng hiện tại đang giữ. Tức là trong mọi thời gian, không có quá một hiệu ứng được kích hoạt. An cũng không muốn sử dụng hiệu ứng từ một hải đăng quá một lần.
Hãy giúp An biết, cậu cần chọn hiệu ứng từ ít nhất bao nhiêu ngọn hải đăng để có thể giữ hiệu ứng liên tục từ thời điểm 0 đến thời điểm $L$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N,L \ (0< N \le 20; 0<L\le 10^8)$;
- $N$ dòng tiếp theo, mỗi dòng bắt đầu bởi một số nguyên $D_i$, và số nguyên $M_i$, tiếp sau đó là $M_i$ số nguyên $T_{i,j}$ $(0<D_i,T_{i,j}\le L; 0<M_i\le10^3)$ - các số nguyên $T_{i,j}$ trên cùng hàng phân biệt đôi một và theo thứ tự tăng dần.
Kết quả
- Kết quả bài toán. Nếu không tìm được một phương án, in ra -1.
Ví dụ
Ví dụ 1
input
4 100
50 3 15 30 55
40 2 0 65
30 2 20 90
20 1 0
output
3
Giải thích
An đến ngọn hải đăng thứ tư và kích hoạt hiệu ứng tại thời điểm đầu tiên $T_{4,1}=0$, có thể nhận hiệu ứng từ lúc 0 phút đến 20 phút. Tiếp tục, cậu nhận hiệu ứng thứ nhất của hải đăng thứ nhất, từ phút 20 đến phút 65. Cuối cùng, cậu nhận hiệu ứng thứ hai của hải đăng thứ hai từ phút 65 đến phút 100.
Comments