#P617. 生存游戏

生存游戏

题目描述

小爱需要坚强地渡过 dd 天,每过一天要消耗一单位的物资,一开始,她有 cc 单位的物资。

过程中有 nn 次补给机会,第 ii 次机会发生在第 xix_i 天结束的时候 ,该机会可以补给 aia_i 单位的物资。

请计算小爱至少需要补给多少次才能坚持 dd 天,如果不可能,输出 Impossible

输入格式

  • 第一行:三个整数 nnccdd
  • 第二行到第 n+1n+1 行:在第 i+1i+1 行有两个整数 xix_iaia_i
  • 输入数据保证 0x1x2x3xnd0\leq x_1\leq x_2\leq x_3\leq \dots\leq x_n\leq d

输出格式

  • 如果能够生存到最后,输出最少补给次数,否则输出 Impossible
3 10 20
5 3
9 4
11 5
3

数据范围

  • 对于 30%30\% 的数据,1n201\leq n\leq 20
  • 对于 60%60\% 的数据,1n2001\leq n\leq 2001ai2001\leq a_i\leq 200
  • 对于 100%100\% 的数据,1n200,0001\leq n\leq 200,000
  • 1cd1,000,000,0001\leq c\leq d\leq 1,000,000,000
  • 1ai1,000,000,0001\leq a_i\leq 1,000,000,000