题目描述
小爱需要坚强地渡过 d 天,每过一天要消耗一单位的物资,一开始,她有 c 单位的物资。
过程中有 n 次补给机会,第 i 次机会发生在第 xi 天结束的时候 ,该机会可以补给 ai 单位的物资。
请计算小爱至少需要补给多少次才能坚持 d 天,如果不可能,输出 Impossible
。
输入格式
- 第一行:三个整数 n,c 与d;
- 第二行到第 n+1 行:在第 i+1 行有两个整数 xi 和 ai;
- 输入数据保证 0≤x1≤x2≤x3≤⋯≤xn≤d
输出格式
- 如果能够生存到最后,输出最少补给次数,否则输出
Impossible
。
3 10 20
5 3
9 4
11 5
3
数据范围
- 对于 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;