【题目描述】

有 $n$ 种矿石。第 $i$ 种每块重量为 $a_i$、价值为 $b_i$，最多有 $c_i$ 块。背包容量为 $m$。

求背包能装入的最大总价值。

【输入格式】

$n$   $m$

$a_1$   $b_1$   $c_1$

$\vdots$

【输出格式】

输出最大总价值。

【样例】

2 10
3 5 2
4 8 3

18

【数据范围】

• $1\le n\le100$
• $0\le m\le10000$
• $1\le a_i\le100$
• $1\le b_i\le10^9$
• $1\le c_i\le10$