← 返回题目列表

AtCoder · tessoku_book_cr

B19. 背包 2

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

配点: 1000 点

这个问题是教育DP竞赛E-背包2 相同的问题。

問題文

在宝箱里 包含 N 项目,每个项目都有 它们的编号最大为 1 减去 N 。
品物 i 的权重是 w_i 的值为 v_i 。

太郎想挑选一些物品带回家。
不过他的背包有容量限制,所以总重量是 W 必须是:
最大可能的总价值是多少?

制約

  • 1 \leq N \leq 100
  • 1 \leq W \leq 10^9
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 1000
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

3 100
55 2
75 3
40 2

出力例 2

4

最好选择第 1 项或第 3 项。


入力例 3

10 1000000000
80000000 99
11000000 119
12000000 150
15000000 174
16000000 168
18000000 190
19000000 187
25000000 273
28000000 307
30000000 319

出力例 3

1986