题目描述

$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$

输出格式

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

题目大意

$n$ 个物品，选取其中若干个物品，使得对选取的这些物品 $\sum w_i\leq W$ 的前提下最大化 $\sum v_i$。

其实就是背包问题。

注意数据范围与上一题不同。

3 8
3 30
4 50
5 60

90

1 1000000000
1000000000 10

10

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

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