1943_算法设计例题：多重背包

给定N种物品和一个容量为C的背包，第i种物品最多有 M_i 件可用，每件的重量是W_i，价值是V_i。问：将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入的第一行为测试样例的个数T，接下来有T个测试样例。

每个测试样例的第一行是物品种数N（1 ≤ N ≤ 100）和背包容量C（C ≤ 10000）。

接下来N行，每行三个正整数，W_i ，V_i 和 M_i （ W_i ≤ 10000,    V_i ≤ 10000,    M_i ≤ 10000 ），分别表示第i种物品的重量 W_i ，价值 V_i ，及个数 M_i 。

对应每个测试样例输出一行，只有一个整数，表示装入背包的物品总价值的最大值。

1
2 8
4 100 2
2 100 4

400