g6-08121. 限购清单 未做

有 $t$ 组数据。每组数据给 $n$ 种商品与容量为 $W$ 的购物车，第 $i$ 种商品单件重量 $w_i$、单件价值 $v_i$，并且最多只能买 $c_i$ 件。求在总重量不超过 $W$ 的前提下能获得的最大总价值。

第一行一个整数 $t$。

接下来 $t$ 组数据，每组格式为：

• 一行两个整数 $n$、$W$；
• 接下来 $n$ 行，每行三个整数 $w_i$、$v_i$、$c_i$。

输出 $t$ 行，每行一个整数，表示该组数据的最大总价值。

输入 1

1
2 5
2 3 2
3 4 1

输出 1

7

买一件第一种（重量 $2$、价值 $3$）和一件第二种（重量 $3$、价值 $4$），总重量 $5$、总价值 $7$。

$1\le t\le 3$，$1\le n\le 100$，$0\le W\le 2000$，$1\le w_i\le 100$，$0\le v_i\le 1000$，$1\le c_i\le 10$，$\sum c_i\le 1000$。答案在 64 位整数内。