题目描述

有一个容量为 W 的背包，有 N 种物品可以挑选，第 i 件物品的体积是 $w_{i}$，价值是 $v_{i}$，且第 i 种物品只有 $m_{i}$ 个。

选择若干个物品装入背包，求背包能装下的最大价值是多少？

输入格式

第一行为一个整数 n 和 W，分别表示宝物种数和采集车的最大载重。

接下来 n 行每行三个整数 $v_{i}$，$w_{i}$，$m_{i}$。

输出格式

输出仅一个整数，表示背包能装下的最大价值。

4 20
3 9 3
5 9 1
9 4 2
8 1 3

47

3 100
9 1 5
5 50 73
3 43 19

53

4 536
4 206 19
8 100 31
4 121 18
2 93 27

40

数据范围与约定

n≤Σ$m_{i}$≤10^4，0≤W≤10^3。