配点: 1000 点
这个问题是教育DP竞赛D - 背包1 与 相同的问题。
問題文
在宝箱里
包含 N 项目,每个项目都有
它们的编号最大为 1 不同编号的点最多为 N 。
品物 i 的权重是 w_i 的值为 v_i 。
太郎想挑选一些物品带回家。
不过他的背包有容量限制,所以总重量是 W 必须是:
最大可能的总价值是多少?
制約
- 1 \leq N \leq 100
- 1 \leq W \leq 100000
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 10^9
- 输入都是整数
入力
输入是按以下格式从标准输入给出的。
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
4 100 25 47 25 53 25 62 25 88
出力例 2
250
您可以选择所有项目。
入力例 3
10 285 29 8000 43 11000 47 10000 51 13000 52 16000 66 14000 72 25000 79 18000 82 23000 86 27000
出力例 3
87000