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;