0239 - ナップザック問題(Medium)

時間制限 1 秒 / メモリ制限 256 MB / 得点 3 / Writer root / x 54 / 統計 /


TLE
1sec
MLE
256MB
得点
3

問題

価値が vi 重さが wi であるような N 種類の品物と、容量が W のナップザックがあります。

次の条件を満たすように、品物を選んでナップザックに入れます:

  • 選んだ品物の価値の合計をできるだけ高くする。
  • 選んだ品物の重さの総和は W を超えない。
  • 同じ種類の品物はいくつでも選ぶことができる。

価値の合計の最大値を求めてください。

入力

N W
v1 w1
v2 w2
:
vN wN

1行目に2つの整数 N、W が空白区切りで1行に与えられる。

続く N 行で i 番目の品物の価値 vi と重さ wi が空白区切りで与えられる。

制約

  • 1 ≦ n ≦ 100
  • 1 ≦ W ≦ 10000
  • 1 ≦ vi ≦ 1000
  • 1 ≦ wi ≦ 1000

出力

価値の合計の最大値を1行に出力する。

入出力例

入力例1

4 8
4 2
5 2
2 1
8 3

出力例1

21

入力例2

2 20
5 9
4 10

出力例2

10

入力例3

3 9
2 1
3 1
5 2

出力例3

27