0881 - ナップザック問題(Alter)

問題

価値が v ,重さが w の n 個の品物がある。
重さの総和が W を超えないように選んだときの価値の総和の最大値を求めよ。
同じ品物は1回しか選べない。

入力

1 行目に品物の数 n, 選べる品物の重さの総和 W が空白区切りで与えられる。

続く n 行に i 番目の品物の価値 v_i と、重さ w_i が与えられる。

出力

重さの総和が W を超えないように品物を選んだときの価値の総和の最大値を出力せよ。出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ n ≦ 20
• 1 ≦ W ≦ 10⁹
• 1 ≦ v_i, w_i ≦ 10⁹

入出力例

入力例1

5 10
20 10
1 3
10 4
4 2
2 1

出力例1

20

入力例2

4 2
10 1
3 3
4 1
5 1

出力例2

15