個数制限付きナップザック問題 II

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

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

• 選んだ品物の価値の合計をできるだけ高くする。
• 選んだ品物の重さの総和は $W$ を超えない。
• $i$ 番目の品物は $m_i$ 個まで選ぶことができる。

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

入力

$N$ $W$
$v_1$ $w_1$ $m_1$
$v_2$ $w_2$ $m_2$
:
$v_N$ $w_N$ $m_N$

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

続く $N$ 行に $i$ 番目の品物の価値、重さ、個数の制限が空白区切りで与えられる。

出力

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

制約

• $1 \le N \le 50$
• $1 \le v_i \le 50$
• $1 \le w_i \le 10^9$
• $1 \le m_i \le 10^9$
• $1 \le W \le 10^9$

入力例 1

4 8
4 3 2
2 1 1
1 2 4
3 2 2

出力例 1

12

入力例 2

2 100
1 1 100
2 1 50

出力例 2

150

入力例 3

5 1000000000
3 5 1000000000
7 6 1000000000
4 4 1000000000
6 8 1000000000
2 5 1000000000

出力例 3

1166666666

---