P3118 [USACO15JAN] Moovie Mooving G
题目描述
Bessie 正在外看电影。调皮的她想在 $L$($1 \leq L \leq 100,000,000$)分钟内连续观看电影来躲避农夫 John。她有 $N$($1 \leq N \leq 20$)部电影可选,每部电影有特定时长和多个放映场次。Bessie 可以在电影放映期间的任意时刻入场或离场,但不能重复观看同一部电影,也不能切换到同一部电影时间重叠的场次。
请判断 Bessie 是否能从时间 $0$ 到时间 $L$ 连续观看电影。若可行,求出达成目标所需观看的最小电影数量(过多电影会让 Bessie 混淆剧情)。
输入格式
第一行输入包含 $N$ 和 $L$。
接下来 $N$ 行描述每部电影:每行以整数时长 $D$($1 \leq D \leq L$)和场次数 $C$($1 \leq C \leq 1000$)开头,随后给出 $C$ 个按升序排列的场次开始时间(范围 $0$ 至 $L$,且互不重复)。
输出格式
输出达成目标所需的最小电影数量。若不可能则输出 $-1$。
说明/提示
Bessie 可以观看第四部电影的首场(时间 $0$ 至 $20$),接着观看第一部电影的首场(时间 $20$ 至 $65$),最后观看第二部电影的末场(时间 $65$ 至 $100$)。