分数: 400 点
问题陈述
你有 N 物品和一袋力量 W。 的 i- 第一项的重量为 w_i 和值为 v_i.
您将选择一些物品并将它们放入包中。 这里,所选物品的总重量最多需要为 W.
您的目标是最大化所选项目的总价值。
约束
- 1 ≤ N ≤ 100
- 1 ≤ W ≤ 10^9
- 1 ≤ w_i ≤ 10^9
- 对于每个 i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.
- 1 ≤ v_i ≤ 10^7
- W,每个 w_i 和 v_i 是整数。
输入
输入由标准输入按以下格式给出:
N W w_1 v_1 w_2 v_2 : w_N v_N
输出
打印所选项目的最大可能总值。
示例输入 1
4 6 2 1 3 4 4 10 3 4
示例输出 1
11
应选择第一项和第三项。
示例输入 2
4 6 2 1 3 7 4 10 3 6
示例输出 2
13
应选择第二项和第四项。
示例输入 3
4 10 1 100 1 100 1 100 1 100
示例输出 3
400
你可以拿走一切。
示例输入 4
4 1 10 100 10 100 10 100 10 100
示例输出 4
0
你什么都不能拿。