题目详情 - 又见01背包 - 南阳理工学院OJ

ID: 911

远端评测题

1000ms

128MiB

难度: (无)

上传者:

有n个重量和价值分别为wi 和 vi 的物品，从这些物品中选择总重量不超过 W

的物品，求所有挑选方案中物品价值总和的最大值。

　　1 <= n <=100

　　1 <= wi <= 10^7

　　1 <= vi <= 100

　　1 <= W <= 10^9

Input

多组测试数据。
每组测试数据第一行输入，n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。

Output

满足题意的最大价值，每组测试数据占一行。

Sample Input

Sample Output

HINT

Source