← 返回题目列表

AtCoder · tessoku_book_s

A19. 背包 1

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

配点: 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