题目描述

有一个贼在偷窃一家商店时发现有N件物品：第i件物品值Vi元，重Wi磅（1≤i≤n），此处Vi和Wi都是整数。他希望带走的东西越值钱越好，但他的背包中最多只能装下W磅的东西（W为整数），小偷可带走某个物品的一部分，小偷最终带走的物品的价值最高是多少？

输入格式

输入第一行为N W（N≤10000，W≤30000），后面N行描述每个物品，每行两个整数，依次为Vi与Wi。

输出格式

输出一行，为小偷最终偷的物品的最大价值（结果取整）。

样例输入

4 50
60 10
100 20
120 30
45 15

样例输出

240

样例解释

该样例中，共有4件物品，背包的最大承重为50磅。最终选取的物品及对应重量、价值如下：

• 选取第一件物品的全部，重量10磅，价值60元；
• 选取第二件物品的全部，重量20磅，价值100元；
• 选取第三件物品的20磅（总重量30磅），对应价值为120×(20/30)=80元； 上述选取的物品总重量为10+20+20=50磅，恰好达到背包最大承重，总价值为60+100+80=240元，这是能带走的最大价值。