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$ となります。