1960_算法设计例题：0_1背包问题（DP）

给定n个物品和一个背包。物品i的重量是w_i，其价值为v_i，背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？

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

每个测试样例的第一行是物品个数n（1 ≤ n ≤ 3500）和背包容量C（C ≤ 13000），接下来n行，每行两个正整数 w_i和 v_i（ w_i ≤ 1000,  v_i ≤ 1000 ），分别表示第i件物品的重量 w_i及其价值 v_i。

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

2
1 2
1 1
2 3
2 3
2 4

1
4