ナップザック問題

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

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

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

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

入力

N W
v1 w1
v2 w2
:
vN wN

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

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

出力

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

制約

• 1 ≤ N ≤ 100
• 1 ≤ v_i ≤ 1000
• 1 ≤ w_i ≤ 1000
• 1 ≤ W ≤ 10000

入力例 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

---