Knapsack 2

题面翻译

\(N\) 个物品被编号为 \(1, 2, \ldots, N\)。对于 \(1 \leq i \leq N\)，物品 \(i\) 的重量是 \(w _ i\)，价值是 \(v _ i\)。

太郎君决定从 \(N\) 个物品中选择一些放入背包中带回家。背包的容量为 \(W\)，带回的物品的总重量不能超过 \(W\)。

请计算太郎君能带回的物品的最大总价值。

输入格式

输入以以下格式从标准输入中提供：

\(N\) \(W\)

\(w _ 1\) \(v _ 1\)

\(w _ 2\) \(v _ 2\)

\(\ldots\)

\(w _ N\) \(v _ N\)

输出格式

输出太郎君能带回的物品的最大总价值。

限制条件

• 所有输入均为整数。
• \(1 \leq N \leq 100\)
• \(1 \leq W \leq 10 ^ 9\)
• \(1 \leq w _ i \leq W\)
• \(1 \leq v _ i \leq 10 ^ 3\)

样例解释 1

可以选择物品 \(1\) 和 \(3\)。这样，总重量为 \(3 + 5 = 8\)，总价值为 \(30 + 60 = 90\)。

样例解释 3

可以选择物品 \(2, 4, 5\)。这样，总重量为 \(5 + 6 + 3 = 14\)，总价值为 \(6 + 6 + 5 = 17\)。

题目描述

\( N \) 個の品物があります。 品物には \( 1,\ 2,\ \ldots,\ N \) と番号が振られています。 各 \( i \) (\( 1\ \leq\ i\ \leq\ N \)) について、品物 \( i \) の重さは \( w_i \) で、価値は \( v_i \) です。

太郎君は、\( N \) 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は \( W \) であり、持ち帰る品物の重さの総和は \( W \) 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

\( N \) \( W \) \( w_1 \) \( v_1 \) \( w_2 \) \( v_2 \) \( : \) \( w_N \) \( v_N \)

输出格式

太郎君が持ち帰る品物の価値の総和の最大値を出力せよ。

样例 #1

样例输入 #1

3 8
3 30
4 50
5 60

样例输出 #1

90

样例 #2

样例输入 #2

1 1000000000
1000000000 10

样例输出 #2

10

样例 #3

样例输入 #3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

样例输出 #3

17

提示

制約

• 入力はすべて整数である。
• \( 1\ \leq\ N\ \leq\ 100 \)
• \( 1\ \leq\ W\ \leq\ 10^9 \)
• \( 1\ \leq\ w_i\ \leq\ W \)
• \( 1\ \leq\ v_i\ \leq\ 10^3 \)

Sample Explanation 1

品物 \( 1,\ 3 \) を選べばよいです。 すると、重さの総和は \( 3\ +\ 5\ =\ 8 \) となり、価値の総和は \( 30\ +\ 60\ =\ 90 \) となります。

Sample Explanation 3

品物 \( 2,\ 4,\ 5 \) を選べばよいです。 すると、重さの総和は \( 5\ +\ 6\ +\ 3\ =\ 14 \) となり、価値の総和は \( 6\ +\ 6\ +\ 5\ =\ 17 \) となります。