分数: 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^9
- 1 \leq w_i \leq W
- 1 \leq v_i \leq 10^3
输入
输入由标准输入按以下格式给出:
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
1 1000000000 1000000000 10
示例输出 2
10
示例输入 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.