奶牛贝西想连续看L (1 <= L <=
100,000,000)分钟的电影,有 N (1
<= N <= 20)部电影可供选择,每部电影会在一天的不同时段放映。
贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影,所以每部电影她最多看到一次。她也不能在看一部电影的过程中,换到另一个正在播放相同电影的放映厅。
请帮贝西计算她能够做到从0到L分钟连续不断地观看电影,如果能,请计算她最少看几部电影就行了。
第一行输入包含N和L。
接下来的N行中,每行描述一部电影。每行从其播放时间D(1<=D<=L)开始,接着是放映次数C(1<=C<=1000)。同一行上的整数C均在0…L之间,并给出电影其中一场放映的开始时间。演出时间均不同,在0…L之间, 并按递增顺序给出。
一个整数,表示贝西实现她的目标所观看的电影的最小数量。如果这是不可能的,输出-1。
4 100
50 3 15 30 55
40 2 0 65
30 2 20 90
20 1 0
3