1946_算法设计例题：分组背包

给出一个背包，背包有容量C，再给出N组物品，每组物品有k_i种，每种物品有对应的体积V_i，价值P_i，每组物品至多选一种，且最多取一件。求用背包装物品，能获得的最大总价值是多少。

文件的第一行一个数T，表示测试用例数。

接下来T个测试用例。

每个测试用例第一行两个数，N, C（N, C < 1000），表示物品的组数和背包的容量

接下来描述N组物品，

每一组的第一行是一个数k_i（k_i < 100），表示该组物品的种类数

接下来的k_i行，每一行是两个数V_i, P_i（V_i < 1.5×C,  P_i < 1000）分别表示物品的体积，价值。

为每个测试用例输出一行结果：所装物品价值的最大值。

1
2 10
2
10 1
3 5
2
2 2
2 3

8