AT_abc442_g [ABC442G] Lightweight Knapsack

$ N $ 種類のアイテムがあります。 $ i $ 種類目のアイテムの **重み** は $ W_i $ 、**価値** は $ V_i $ であり、あなたはこれを $ K_i $ 個持っています。 これらの $ K_1+\dots+K_N $ 個のアイテムの中から、重みの総和が $ C $ を超えないようにいくつか（ $ 0 $ 個でもよい）を選ぶとき、選んだアイテムの価値の総和が最大でいくつになるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C $ $ W_1 $ $ V_1 $ $ K_1 $ $ W_2 $ $ V_2 $ $ K_2 $ $ \vdots $ $ W_N $ $ V_N $ $ K_N $

答えを出力せよ。

### Sample Explanation 1 $ 1 $ 種類目のアイテムを $ 1 $ 個、 $ 2 $ 種類目のアイテムを $ 2 $ 個、 $ 3 $ 種類目のアイテムを $ 1 $ 個選ぶと、重みの総和は $ 3\times 1+1\times 2+2\times 1=7\ (\leq C) $ 、 価値の総和は $ 5\times 1+2\times 2+7\times 1=16 $ となり、これが最大です。 ### Sample Explanation 2 アイテムを一つも選ぶことができません。 ### Constraints - $ 1\leq N \leq 2\times 10^5 $ - $ 1\leq C \leq 2\times 10^9 $ - $ 1\leq W_i \leq 3 $ - $ 1\leq V_i \leq 10^9 $ - $ 1\leq K_i \leq 10^9 $ - 入力は全て整数