TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3212
  • 問題
  • P3212看电影
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    何老板获得了一张电影院的免费观影卡,可以免费连续看L分钟的电影。该影院有N部电影可供选择,每部电影会在当天的不同时段放映。

    何老板可以在一部电影播放过程中的任何时间进入或退出放映厅。但他不愿意重复看到一部电影,所以每部电影他最多看一次。他也不能在看一部电影的过程中,换到另一个正在播放相同电影的放映厅。

    请帮何老板计算他能否做到从0到L分钟连续不断地观看电影,如果能,请计算他最少看几部电影就行了(一部电影只要看了,即使没有看完也算看了该电影)。

    入力形式

    第一行,两个整数N和L
    接下来N行,每行描述一部电影的信息:
     第一个整数表示该电影的时间长度,第二个整数K表示该电影播放的场数,接下来K个整数,分别表示每场开始的时间。
     同一部电影的K次播放时间都是不同的,电影开始时间的范围在0..L以内,数据按时间升序给出。

    出力形式

    一个整数,表示所求的结果。如果无解,输出-1

    サンプル入力

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

    サンプル出力

    3

    ヒント

    样例1说明:何老板在第0到20分钟观看第4部电影,在20到65分钟观看第1部电影,在第65到第100分钟他观看第2部电影。

    1 <= N <= 20
    K<=1000
    1 <= L <= 100,000,000


    ソース  【USACO 2015 Jan Gold】翻译 By BossH