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

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

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

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

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

入力

N W
v1 w1 m1 
v2 w2 m2 
:
vN wN mN 

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

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

出力

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

制約

• 1 ≤ N ≤ 100
• 1 ≤ v_i ≤ 1,000
• 1 ≤ w_i ≤ 1,000
• 1 ≤ m_i ≤ 10,000
• 1 ≤ W ≤ 10,000

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

---