配点 : $400$ 点

問題文

あなたは $N$ 個の物と、強度 $W$ のバッグを持っています。 $i$ 個目の物は、重さが $w_i$ で価値が $v_i$ です。

あなたは、物のうちいくつかを選び、バッグに入れます。 ただし、選んだ物の重さの和は $W$ 以下でなくてはいけません。

あなたは、バッグに入れた物の価値の総和を最大化したいです。

制約

• $1 \leq N \leq 100$
• $1 \leq W \leq 10^9$
• $1 \leq w_i \leq 10^9$
• すべての $i = 2,3,...,N$ について、$w_1 \leq w_i \leq w_1 + 3$
• $1 \leq v_i \leq 10^7$
• $W, w_i, v_i$ はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $W$

$w_1$ $v_1$

$w_2$ $v_2$

:

$w_N$ $v_N$

出力

価値の総和の最大値を出力する。

4 6
2 1
3 4
4 10
3 4

11

$1, 3$ 個目の物を選ぶと良いです。

4 6
2 1
3 7
4 10
3 6

13

$2, 4$ 個目の物を選ぶと良いです。

4 10
1 100
1 100
1 100
1 100

400

すべての物が選べます。

4 1
10 100
10 100
10 100
10 100

0

$1$ 個も物が選べません。