#P5433. Moovie Mooving

Moovie Mooving

题目描述

贝西出去看电影了。她总是淘气,所以 决定为L{L(}1<=L<=100000000{1<=L<=100000000)}躲避农民约翰 分钟,在这段时间里她想不间断地看电影。 她有N{N(}1<=N<=20{1<=N<=20)}部电影可供选择,每部电影都有一个 一天中的特定持续时间和一组演出时间。贝西·梅 在电影放映期间的任何时间进入和退出电影,但是 她不想两次看同一部电影,她也不能 切换到同一电影的另一个放映时间,该时间与 当前放映时间。

帮助贝西确定她是否有可能实现目标 从时间0{0}到时间L{L}连续观看电影的目标。如果 也就是说,确定她需要看的电影的最少数量 实现这一目标(如果贝西观看,她会对情节线感到困惑 太多的电影)。

输入格式

第一行输入包含N{N}L{L}

接下来的N{N}行分别描述了一部电影。它们从整数开始 持续时间D{D(}1<=D<=L{1<=D<=L)}和放映次数C{C(}1<=C<={1<=C<=} 1000).{1000). }同一行上剩余的C{C}整数分别位于 范围0...50{0...50} 并给出 电影演出时间不同,范围为0...50{0...50}、 并在 递增顺序。

输出格式

一个整数,表示贝西观看的电影的最小数量 需要看到实现她的目标。如果这是不可能的,输出1{-1} 相反

样例

输入样例

4 100
50 3 15 30 55
40 2 0 65
30 2 20 90
20 1 0

输出样例

3

提示

贝西应该从0{0}开始参加第四部电影的第一场放映 到时间20{20}。然后她看了第一部电影的第一场演出 从时间20{20}到时间65{65}。最后她看了最后一场演出 第二部电影,从《时代》65{65}到《时代》100{100}