0238 - ナップザック問題(Easy)

問題

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

入力

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

続く n 行には、それぞれの品物の情報が書かれている。そのうち、i 行目には、空白で区切られた整数 v_i, w_i が書かれており、i 番目の品物の価値が v_i で 重さが w_iであることを表す。

制約

• 1 ≦ n ≦ 100
• 1 ≦ W ≦ 10000
• 1 ≦ v_i ≦ 1000
• 1 ≦ w_i ≦ 1000

出力

1行に、重さの総和 W を超えないように荷物を選ぶときの価値の総和の最大値を出力する。

入出力例

入力例1

4 5
2 3
1 2
3 4
2 2

出力例1

4

1, 4番目の荷物を選ぶと、重さの総和 5 で、価値の総和が 4 となりこれが最大となる。

入力例2

1 1
451 4

出力例2

0

重さ 1 以下で選べる荷物がないので、0 を出力する。

入力例3

2 10
5 9
4 10

出力例3

5

1 番目の荷物を選ぶと価値が 5 となりこれが最大となる。