[七中七模]匹诺曹的鼻子长

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file nose.in Output file nose.out

【题目描述】


话说在某日,匹诺曹见到了上帝。上帝给了他n 个鼻子,每个鼻子都有价格(第i 个鼻子价格为a[i])与长度(第i 个鼻子长度为b[i]),匹诺曹有m 元,请你算出他的鼻子最多可以达到多长(可以选择任意数量的鼻子,多个鼻子长度叠加)。


【输入格式】


输入文件为nose.in。

第1 行,2 个数n,m。

第2 到n+1 行,每行2 个数,之间分别用一个空格隔开,表示价格和长度。


【输出格式】


输出文件为nose.out。

输出仅一行,即鼻子的最大长度。


【样例输入】

2 100

50 1

50 2

【样例输出】

3

【提示】


两个鼻子都要。

对于50%的数据,n<=100;

对于100%的数据,n<=1000,m,a[i],b[i]<=maxint。


【来源】

常可神牛原创