Problem1016--打怪升级

1016: 打怪升级

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

    对于多数 RPG游戏来说,除了剧情就是打怪升级。本题的任务是用最短的时间取得所有战斗的胜利。这些 战斗必须按照特定的顺序进行,每打赢一场,都可能会获得一些补药,用来提升力量。本题只有两种补药: “加 1 药”和“乘 2 药”,分别让你的力量值加 1 和乘以 2。战斗时间取决于你的力量。每场战斗可以用 6 个参数描述:p1, p2, t1, t2, w1, w2。如果你的力量小于 p1,你将 输掉战斗;如果你的力量大于 p2,需要 t2秒赢得战斗;如果力量位于 p1和 p2(包括 p1和 p2),战斗时间从 t1线 性递减到 t2。比如 p1=50,p2=75,t1=40,t2=15,你的力量为 55,则战斗获胜需要 35秒。注意,战斗时间可能 不是整数。最后两个参数 w1和 w2分别表示战斗胜利后获得的“加 1 药”和“乘 2 药”的数量。注意,你不一定 要立刻使用这些补药,可以在需要的时候再用,但不能在战斗中使用补药。按顺序给出每场战斗的参数,输出赢得所有战斗所需的最短总时间。战斗必须按顺序进行,且不能跳过任 何一场战斗。 

Input

    输入最多包含 25组测试数据。每组数据第一行为两个整数 n 和 p(1<=n<=1000, 1<=p<=100),即战斗的场 数和你的初始力量值。以下 n 行每行 6 个整数 p1, p2, t1, t2, w1, w2(1<=p1<p2<=100, 1<=t2<t1<=100, 0<=w1,w2<=10),按顺序给出各场战斗的参数。输入结束标志为 n=p=0。 

Output

    对于每组数据,输出最短总时间(单位:秒),保留两位小数。如果无解,输出“Impossible”(不含引 号)。 

Sample Input Copy

1 55
50 75 40 15 10 0
2 55
50 75 40 15 10 0
50 75 40 15 10 0
3 1
1 2 2 1 0 5
1 2 2 1 1 0
1 100 100 1 0 0
1 7
4 15 35 23 0 0
1 1
2 3 2 1 0 0
0 0 

Sample Output Copy

35.00
60.00
41.00
31.73
Impossible