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は、このサンプルケースです。