配点 : $100$ 点

問題文

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

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

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

制約

• 入力はすべて整数である。
• $1 \leq N \leq 100$
• $1 \leq W \leq 10^5$
• $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$

出力

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

3 8
3 30
4 50
5 60

90

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

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

5000000000

答えは 32-bit 整数型に収まらない場合があります。

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

17

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