题目描述

有一个贼在偷窃一家商店时发现有 $N$ 件物品：第 $i$ 件物品价值 $V_i$ 元，重 $W_i$ 磅（$1 \leq i \leq N$），$V_i$ 和 $W_i$ 都是整数。他希望带走的东西越值钱越好，但他的背包最多只能装下 $W$ 磅的东西（$W$ 为整数）。小偷可以带走某个物品的一部分（即可将物品切割，按重量比例获得相应价值）。请问小偷最终带走的物品的最高总价值是多少？

输入格式

第一行包含两个整数 $N$ 和 $W$，分别表示物品的数量和背包的最大承重。
接下来 $N$ 行，每行两个整数 $V_i$ 和 $W_i$，分别表示第 $i$ 件物品的价值和重量。

输出格式

输出一行一个整数，表示能获得的最大总价值（结果取整）。

样例

4 50
60 10
100 20
120 30
45 15

240

样例解释
共有 $4$ 件物品，背包承重 $50$ 磅。最优方案：

• 第 $1$ 件：取全部，重量 $10$，价值 $60$；
• 第 $2$ 件：取全部，重量 $20$，价值 $100$；
• 第 $3$ 件：取 $20$ 磅（$\frac{2}{3}$），价值 $120 \times \frac{20}{30} = 80$；
• 第 $4$ 件不取。

总重量 $10+20+20=50$，总价值 $60+100+80=240$，为最大值。

数据范围

• $1 \le N \le 10000$
• $1 \le W \le 30000$
• $1 \le V_i, W_i \le 30000$（价值与重量为正整数）