【题目描述】

话说在某日，匹诺曹见到了上帝。上帝给了他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。

【来源】

常可神牛原创