题目描述
有一个最大载重为 $W$ 的采集车，洞穴里总共有 $n$ 种宝物，每种宝物的价值为 $v_i$，重量为 $w_i$，每种宝物有 $m_i$ 件。请你在采集车不超载的前提下，选择一些宝物装进采集车，使他们的价值和最大。
输入
第一行为两个整数 $n$ 和 $W$，分别表示宝物种数和采集车的最大载重。接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。
输出
输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。
样例输入输出
输入#1
复制
4 20
3 9 3
5 9 1
9 4 2
8 1 3
提示
对于 $30\%$ 的数据，$n \leq \sum{m_i} \leq 10^4$，$0 \leq W \leq 10^3$。
对于 $100\%$ 的数据，$n \leq \sum{m_i} \leq 10^4$，$0 \leq W \leq 10^3$，$1\leq n \leq 100$。