#E. Spider Mine 的排布

    传统题 1000ms 128MiB

Spider Mine 的排布

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

占星教为了在各门派之争中立于不败之地,下设许多“堂”来研究各种新奇的战术,本 周,他们的课题就是:如何将一排排满的Spider Mine(蜘蛛雷)封锁一个路口。

由于SC 中不同的蜘蛛雷所控制的范围不同,为了简化问题,我们将告诉你现在有多少 个可选位置来埋雷,以及每个位置上雷的控制范围。我们希望知道这些雷是否可以封锁路口, 以及如果可以最少取出其中的多少颗就可以封锁路口了。(当然要假设别人没有反隐的东东 咯~~)。

Format

Input

输入数据共N+1 行

第1 行为两个正整数N,M,分别表示有多少颗可选的雷,以及路口的长度(表示[1,M]的闭区间)

第 2-n+1 行每行两个正整数,表示每个蜘蛛雷可控制的范围。

Output

输出数据共一行

如果蜘蛛雷可以控制整个路口,那么输出最少需要的雷数。

如果不能控制,那么输出“Impossible”。

Samples

3 10
1 5 3 6 6 10
2
3 10
1 2 3 6 8 10
Impossible

Limitation

对于 30%的数据,1<=N<=100,1<=M<=300;

对于 70%的数据,1<=N<=10000,1<=M<=3000000;

对于 100%的数据,1<=N<=1000000,1<=M<=232-1;

7月7日简单题

未认领
状态
已结束
题目
5
开始时间
2023-7-1 0:00
截止时间
2023-8-31 23:59
可延期
24 小时