AT_abc442_g [ABC442G] Lightweight Knapsack

There are $ N $ types of items. The $ i $ -th type of item has **weight** $ W_i $ and **value** $ V_i $ , and you have $ K_i $ of them. When choosing some (possibly zero) items from these $ K_1+\dots+K_N $ items so that the total weight does not exceed $ C $ , find the maximum possible total value of the chosen items.

The input is given from Standard Input in the following format: > $ N $ $ C $ > > $ W_1 $ $ V_1 $ $ K_1 $ > > $ W_2 $ $ V_2 $ $ K_2 $ > > $ \vdots $ > > $ W_N $ $ V_N $ $ K_N $

Print the answer.

### Sample Explanation 1 If you choose $ 1 $ item of the $ 1 $ -st type, $ 2 $ items of the $ 2 $ -nd type, and $ 1 $ item of the $ 3 $ -rd type, the total weight is $ 3\times 1+1\times 2+2\times 1=7\ (\leq C) $ and the total value is $ 5\times 1+2\times 2+7\times 1=16 $ , which is the maximum. ### Sample Explanation 2 You cannot choose any items. ### 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 $ - All input values are integers.