问题2112--骨头收藏家

2112: 骨头收藏家

时间限制: 1 Sec  内存限制: 128 MB
提交: 5  解决: 5
[提交] [状态] [讨论版] [命题人:]

题目描述

有位骨头收藏家喜欢收集各种各样的骨头，不同的骨头有不同的体积和价值。这个收藏家有一个体积为V 的背包，请计算他可以收藏的最大价值。

输入

第1行包含一个整数T ，表示测试用例的数量。每个测试用例都包含3行，第1行包含两个整数N、V （N ≤1000，V ≤1000），分别表示骨头的数量和背包的体积；第2行包含N 个整数，表示每个骨头的价值；第3行包含N 个整数，表示每个骨头的体积。



输出

对每个测试用例，都单行输出可以得到的最大价值（该数小于231 ）。

样例输入 Copy 

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

样例输出 Copy 

14

来源/分类

动态规划算法 背包问题 
[提交] [状态]