问题 A: 电影

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:43 通过:14

题目描述

奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影,有 N (1 <= N <= 20)部电影可供选择,每部电影会在一天的不同时段放映。
贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影,所以每部电影她最多看到一次。她也不能在看一部电影的过程中,换到另一个正在播放相同电影的放映厅。
请帮贝西计算她能够做到从0L分钟连续不断地观看电影,如果能,请计算她最少看几部电影就行了。

输入格式

第一行输入包含NL
接下来的N行中,每行描述一部电影。每行从其播放时间D1<=D<=L)开始,接着是放映次数C1<=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

数据范围与提示

贝西应该观看第四部电影中的第一次放映在0-20,然后她观看第一部电影的映在20-65。最后,她观看第二部电影的最后一次放映在65-100。