分数: 100 点
问题陈述
有 N 项目,已编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N),项目 i 的权重为 w_i 和值为 v_i.
太郎决定选择一些 N 物品并用背包将它们带回家。 背包的容量为 W,这意味着所取物品的重量之和最多不得超过 W.
找出太郎带回家的物品价值的最大可能总和。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 100
- 1 \leq W \leq 10^5
- 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
3 8 3 30 4 50 5 60
示例输出 1
90
项目 应采取 1 和 3 。 那么权重之和就是 3 + 5 = 8,值的总和为 30 + 60 = 90.
示例输入 2
5 5 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000
示例输出 2
5000000000
答案可能不适合 32 位整数类型。
示例输入 3
6 15 6 5 5 6 6 4 6 6 3 5 7 2
示例输出 3
17
项目 应采取 2, 4 和 5 。 那么权重之和就是 5 + 6 + 3 = 14,值的总和为 6 + 6 + 5 = 17.