问题2783--魔法药水

2783: 魔法药水

时间限制: 1 Sec  内存限制: 128 MB
提交: 227  解决: 17
[状态] [讨论版] [提交] [命题人:]
题目描述
小A终于来到了最后一题。小明翻找自己的背包,发现了很多能够提升自己能力值的药水。小A共发现了n种药水,第i种药水有ai瓶,使用后能使能力值加bi。但相同种类的药水,是不能连续使用的。小A觉得自己至少将能力值提升X(X>=1),才有把握AK这场新生赛。药水的味道并不好,小明想尽量少的使用药水。你能告诉小A,他至少使用多少瓶药水, 才能使自己的能力提升至少X?
输入
第一行包含两个整数n,X(1≤n≤1000,1≤X≤10,000,000,000,000,000); 接下来n行,每行包括两个整数ai,bi(1≤ai,bi≤10,000,000),代表第i种药水有ai瓶,使用后能提示能力值bi。
输出
如果小A不能使自己的能力提升至少X,输出“-1”;否则输出小A最少使用的药水的数量。
样例输入 Copy
2 1000
10 200
5 1
样例输出 Copy
9