LCM Knapsack

配点 : $300$ 点

問題文

$N$ 個の品物があります。品物には $1, 2, \ldots , N$ と番号が振られています。各 $i \ (1 ≦ i ≦ N)$ について、品物 $i$ の重さは $w_i$ で価値は $v_i$ です。

mts くんは $N$ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。ただし、選んだ品物 $\{ x_1, \ldots , x_K \}$ が下記の条件を満たす場合、かつその場合に限り、ナップサックに入れて持ち帰ることができます。ここで、$K$ は選んだ品物の個数、$x_j \ (1 ≦ j ≦ K)$ は選んだ品物の番号を表します。

• $\mathrm{lcm}(w_{x_1}, \ldots , w_{x_K}) \leq W$

mts くんが持ち帰る品物の価値の総和の最大値を求めてください。より厳密には、$\mathrm{lcm}(w_{x_1}, \ldots , w_{x_K}) \leq W$ を満たす品物の選び方 $\{ x_1, \ldots , x_K \}$ における $\sum_{j = 1}^{K} v_{x_j}$ の最大値を求めてください。

ただし、$\mathrm{lcm}(a_1, \ldots , a_n)$ は $n \geq 2$ のとき $\{ a_1, \ldots , a_n \}$ の最小公倍数を、$n = 1$ のとき $a_1$ を、$n = 0$ のとき（つまり品物を一つも選ばないとき）$1$ をそれぞれ表すものとします。

制約

• $1 \leq N \leq 100$
• $1 \leq W \leq 10^4$
• $1 \leq w_i \leq 10^3$
• $1 \leq v_i \leq 10^9$
• 入力は全て整数である

入力

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

出力

mts くんが持ち帰る品物の価値の総和の最大値を出力してください。

サンプル 1

3 15
3 10
4 20
5 30

40

品物の選び方として次の $8$ 通りがあります。

• 品物を一つも選ばない場合、条件を満たし、価値の総和は $0$
• 品物 $\{ 1 \}$ を選ぶ場合、$\mathrm{lcm}(w_{1}) = \mathrm{lcm}(3) = 3$ であり、価値の総和は $10$
• 品物 $\{ 2 \}$ を選ぶ場合、$\mathrm{lcm}(w_{2}) = \mathrm{lcm}(4) = 4$ であり、価値の総和は $20$
• 品物 $\{ 3 \}$ を選ぶ場合、$\mathrm{lcm}(w_{3}) = \mathrm{lcm}(5) = 5$ であり、価値の総和は $30$
• 品物 $\{ 1, 2 \}$ を選ぶ場合、$\mathrm{lcm}(w_{1}, w_{2}) = \mathrm{lcm}(3, 4) = 12$ であり、価値の総和は $30$
• 品物 $\{ 1, 3 \}$ を選ぶ場合、$\mathrm{lcm}(w_{1}, w_{3}) = \mathrm{lcm}(3, 5) = 15$ であり、価値の総和は $40$
• 品物 $\{ 2, 3 \}$ を選ぶ場合、$\mathrm{lcm}(w_{2}, w_{3}) = \mathrm{lcm}(4, 5) = 20$ であり、価値の総和は $50$
• 品物 $\{ 1, 2, 3 \}$ を選ぶ場合、$\mathrm{lcm}(w_{1}, w_{2}, w_{3}) = \mathrm{lcm}(3, 4, 5) = 60$ であり、価値の総和は $60$

このうち、条件を満たす選び方において、価値の総和の最大値は $40$ です。

サンプル 2

4 10
12 100
34 200
56 300
78 400

0

品物を一つも持ち帰ることができない場合があります。

サンプル 3

5 100
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000

5000000000

答えは 32-bit 整数型に収まらない場合があります。