ナップサック問題 5 R(Beta)編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

N 種類の品物の重さ wi と価値 vi が与えられます。
重さが W を超えないように選んだ時の価値の総和の最大値を求めてください。

入力される値

1 行目に整数の個数を表す整数 N と整数 W が与えられ、続く N 行にそれぞれの品物の重さと価値が与えられる。

N W
w_1 v_1
w_2 v_2
...
w_N v_N

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・1 ≦ N ≦ 10^5
・1 ≦ W ≦ 100
・1 ≦ w_i ≦ 10 (1 ≦ i ≦ N)
・1 ≦ v_i ≦ 100 (1 ≦ i ≦ N)