Moovie Mooving#11193
Bessie is out at the movies. Being mischievous as always, she has decided to hide from Farmer John for minutes, during which she wants to watch movies continuously.
She has movies to choose from, each with a fixed duration and a set of showtimes throughout the day. Bessie may enter or leave a movie at any time during one of its showtimes. However, she may not watch the same movie more than once, and she cannot switch to another showing of the same movie if that showing overlaps the one she is currently watching.
Help Bessie determine whether it is possible for her to watch movies continuously from time through time . If it is possible, determine the minimum number of different movies she needs to watch to achieve this goal (Bessie gets confused by complicated plot lines if she watches too many movies).
The first line contains two integers, n~(1 \le n \le 20) and l~(1 \le l \le 10^8).
The next lines each describe one movie. Each line begins with its integer duration d~(1 \le d \le l) and the number of showtimes c~(1 \le c \le 1000). The remaining integers on the same line are each in the range and specify the starting time of one of the movie's showings. The showtimes are distinct, lie in the range , and are given in increasing order.
Print one integer indicating the minimum number of movies Bessie needs to watch to achieve her goal. If this is impossible, print .
Bessie should watch the first showing of the fourth movie from time to time . She then watches the first showing of the first movie from time to time . Finally, she watches the last showing of the second movie from time to time .
Example 1