016 - ナップサック問題その2

2018/1/25 バグがあったので、直してRejudgeしました。

問題

重さと価値が、それぞれw_i,v_iであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。

入力

n W
w1 v1
w2 v2
...
wn vn

1 行目に整数 n, W が与えられる。

これは、それぞれ品物の数と、耐えられる重さの最大値を表す。

2 行目からn+1 行目に整数 w_i, v_i(1 <= i <= n) が与えられる。

それぞれ、品物iの重さと価値を表す。

出力

答えを出力してください。

出力の最後の改行を忘れないようにしてください

制約

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

• 1 ≦ n ≦ 100
• 1 ≦ W ≦ 10⁹
• 1 ≦ w_i ≦ 10⁷
• 1 ≦ v_i ≦ 100

入出力例

入力例

4 5
2 3
1 2
3 4
2 2

出力例

7

text.txtは、このサンプルケースです。