配点: 1000 点
这个问题是教育DP竞赛E-背包2 相同的问题。
問題文
在宝箱里
包含 N 项目,每个项目都有
它们的编号最大为 1 减去 N 。
品物 i 的权重是 w_i 的值为 v_i 。
太郎想挑选一些物品带回家。
不过他的背包有容量限制,所以总重量是 W 必须是:
最大可能的总价值是多少?
制約
- 1 \leq N \leq 100
- 1 \leq W \leq 10^9
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 1000
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N W w_1 v_1 w_2 v_2 : w_N v_N
出力
请以整数形式输出答案。
入力例 1
4 7 3 13 3 17 5 29 1 10
出力例 1
40
例如,如果选择项目 1、项目 2 和项目 4,则总值为 13+17+10=40 。
对于
总值 41 没有其他方法可以做到这一点。
入力例 2
3 100 55 2 75 3 40 2
出力例 2
4
最好选择第 1 项或第 3 项。
入力例 3
10 1000000000 80000000 99 11000000 119 12000000 150 15000000 174 16000000 168 18000000 190 19000000 187 25000000 273 28000000 307 30000000 319
出力例 3
1986