← 返回题目列表

AtCoder · arc073_b

D. 简单的背包

中文机器翻译题面 查看原题

分数: 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

你什么都不能拿。