Moovie Mooving

题目描述

贝茜在看电影。一如既往地调皮，她决定躲避农夫约翰共 $L$（$1 <= L <= 100,000,000$）分钟，在这段时间里她想要连续不断地看电影。\n\n她有 $N$（$1 <= N <= 20$）部电影可选，每部电影都有固定的时长，以及当天的一组放映时间。贝茜可以在某次放映期间的任意时刻进入或离开影院，但她不希望同一部电影看两次；并且她不能切换到同一部电影中与当前放映场次发生重叠的另一场次。\n\n请帮助贝茜判断她是否可以从时间 $0$ 一直连续观看到时间 $L$。如果可以，求她为达成目标所需观看的电影最少数量（电影看太多会让贝茜把剧情搞混）。

输入格式

第一行输入包含 $N$ 和 $L$。\n\n接下来 $N$ 行每行描述一部电影。每行开头是该电影的整数时长 $D$（$1 <= D <= L$）以及放映场次数 $C$（$1 <= C <= 1000$）。同一行接下来的 $C$ 个整数每个都在 $0..L$ 范围内，表示该电影某一场放映的开始时间。放映时间两两不同，位于 $0..L$ 范围内，并按递增顺序给出。

输出格式

输出一个整数，表示贝茜为达成目标所需观看的最少电影数量。如果无法做到，输出 $-1$。

4 100\n50 3 15 30 55\n40 2 0 65\n30 2 20 90\n20 1 0

3

提示

SOLUTION NOTES:\n\n贝茜应当参加第 4 部电影的第一场放映，从时间 0 看到时间 20。然后她观看第 1 部电影的第一场放映，从时间 20 看到时间 65。最后她观看第 2 部电影的最后一场放映，从时间 65 看到时间 100。

标签: USACO|2015|Gold

来源

USACO|2015|Gold