1556: 生存游戏
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:2
Solved:2
Description
小爱需要坚强地渡过 d 天,每过一天要消耗一个单位的物资,如果在中途物没有物资,她就输了。一开始,小爱有 c 个单位的物资。
游戏中有 nn 次补给机会,第 ii 次补给机会在第 xi天结束的时候 ,这次机会可以补给 ai 个单位的物资。
请帮助小爱设计一个在补给最小次数的状态下渡过游戏的方法。如果无法坚持到最后,输出 Impossible。
游戏中有 nn 次补给机会,第 ii 次补给机会在第 xi天结束的时候 ,这次机会可以补给 ai 个单位的物资。
请帮助小爱设计一个在补给最小次数的状态下渡过游戏的方法。如果无法坚持到最后,输出 Impossible。
Input
第一行:三个整数 n,c 与d;
第二行到第 n+1 行:在第i+1 行有两个整数xi 和 ai ;
输入数据保证0≤x1 ≤x2 ≤x3 ≤⋯≤xn≤d
第二行到第 n+1 行:在第i+1 行有两个整数xi 和 ai ;
输入数据保证0≤x1 ≤x2 ≤x3 ≤⋯≤xn≤d
Output
如果能够生存到最后,输出最少补给次数,否则输出 Impossible。
Sample Input Copy
3 10 20
5 3
9 4
11 5
Sample Output Copy
3
HINT
对于 30% 的数据,1≤n≤20;
对于 60% 的数据,1≤n≤200,1≤ai ≤200;
对于 100% 的数据,1≤n≤200,000;
1≤c≤d≤1,000,000,000;
1≤ai ≤1,000,000,000;
对于 60% 的数据,1≤n≤200,1≤ai ≤200;
对于 100% 的数据,1≤n≤200,000;
1≤c≤d≤1,000,000,000;
1≤ai ≤1,000,000,000;