1279: 简单的背包问题
内存限制：32 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：463
解决：45
题目描述
相信大家都学过背包问题了吧，那么现在我就考大家一个问题。有n个物品，每个物品有它的重量w，价值v，现在有一个容量为W的背包，问你在不超过背包容量的情况下，能装下的物品的最大价值是多少。
T <= 100代表样例数
1 <= n <= 100 物品数
1 <= W <= 100000 背包的容量
1 <= wi <= 100000 每个物品的重量
对于每个i=2,3,…,N, w1 ≤ wi ≤ w1+3.
1 <= vi <= 100000 每个物品的价值
T <= 100代表样例数
1 <= n <= 100 物品数
1 <= W <= 100000 背包的容量
1 <= wi <= 100000 每个物品的重量
对于每个i=2,3,…,N, w1 ≤ wi ≤ w1+3.
1 <= vi <= 100000 每个物品的价值
输入
输入格式：
T
n W
w1 v1
w2 v2
:
wn vn
T
n W
w1 v1
w2 v2
:
wn vn
输出
输出占一行，代表最大能装下物品的价值。
样例输入 复制
2
4 6
2 1
3 4
4 10
3 4
4 6
2 1
3 7
4 10
3 6
样例输出 复制
11
13