### 问题描述 在冒险岛的深处，小萌探索到了一个传说中的魔法果实园。这里满是各种神奇的魔法果实，吃了可以增加不同的魔法能量。 小萌想带一些魔法果实回去，但是他的背包空间有限。看着这些琳琅满目的魔法果实，小萌很是纠结，决定选择一些最有价值的果实带回去。 小萌对果园里的魔法果实进行了整理，他发现每种果实都有一颗或者多颗。他估算了下每种魔法果实能增加的魔法能量，然后开始了筛选工作：小萌有一个最大容量为 $W$ 的背包，果园里总共有 $n$ 种魔法果实，每种果实能增加的魔法能量为 $v_i$，重量为 $w_i$，每种魔法果实有 $m_i$ 颗。小萌希望在背包不超重的前提下，选择一些魔法果实装进背包，使得他们能增加的魔法能量最大。 ### 输入格式 第一行为一个整数 $n$ 和 $W$，分别表示魔法果实种数和背包的最大容量。 接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$，分别表示每种果实能增加的魔法能量，重量，每种魔法果实颗数。 ### 输出格式 输出仅一个整数，表示在背包不超重的情况下收集的魔法果实能增加的最大魔法能量。 ### 样例输入 ```text 2 4 2 3 2 1 2 3 ``` ### 样例输出 ```text 2 ``` ### 说明 样例中，最优方案是： 第一种魔法果实 $1$ 个，能量 $2$。第二种魔法果实 $0$ 个，能量 $0$。最大能量为 $2$。 或者，第一种魔法果实 $0$ 个，能量 $0$。第二种魔法果实 $2$ 个，能量 $2$。最大能量为 $2$。 因此，最大魔法能量为 $2$。 ### 评测数据规模 对于 $50$% 的评测数据，$n\leq \sum m_i\leq 10^4$，$0\le W\leq 10^3$。 对于 $100$% 的评测数据，$n\leq \sum m_i \leq 10^5$，$0\le W\leq 4\times 10^4$，$1\leq n\le 100$。