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

時間制限 1 秒 / メモリ制限 64 MB / 得点 5 / x 4 /


TLE
1sec
MLE
64MB
得点
5

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

問題

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

入力

n W
w1 v1
w2 v2
...
wn vn

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

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

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

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

出力

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

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

制約

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

  • 1 ≦ n ≦ 100
  • 1 ≦ W ≦ 109
  • 1 ≦ wi ≦ 107
  • 1 ≦ vi ≦ 100

入出力例

入力例

4 5
2 3
1 2
3 4
2 2

出力例

7

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