AT_abc442_g [ABC442G] Lightweight Knapsack

有 $N$ 种物品。第 $i$ 种物品的重量为 $W_i$，价值为 $V_i$，你拥有该种物品的数量为 $K_i$。 从这 $K_1+\dots+K_N$ 个物品中选择若干个（可以为零个），在总重量不超过 $C$ 的前提下，求所选物品的最大总价值。

输入从标准输入按以下格式给出： > $N$ $C$ > > $W_1$ $V_1$ $K_1$ > > $W_2$ $V_2$ $K_2$ > > $\vdots$ > > $W_N$ $V_N$ $K_N$ **限制条件** - $1 \le N \le 2 \times 10^5$ - $1 \le C \le 2 \times 10^9$ - $1 \le W_i \le 3$ - $1 \le V_i \le 10^9$ - $1 \le K_i \le 10^9$ - 所有输入值均为整数。

打印答案。

**样例 1 解释** 如果你选择 $1$ 个第 $1$ 种物品、$2$ 个第 $2$ 种物品和 $1$ 个第 $3$ 种物品，总重量为 $3 \times 1 + 1 \times 2 + 2 \times 1 = 7 \ (\le C)$，总价值为 $5 \times 1 + 2 \times 2 + 7 \times 1 = 16$，这是可能的最大值。