算法设计与分析

还是收集控

动态规划典型题(5)- 还是收集控

Description

Teddy是著名的旅行家,同时也是著名的收集控。

这回Teddy旅行到了乡间集市,集市上当然也有各种各样好玩的东西,而且,重要的是,每种物品随便买,要多少有多少!

现在问题又来了:

给定每种物品的大小和价值,以及Teddy的背包容量,Teddy最多能带走价值多少的物品?

Input

多组输入样例,第一行一个整数T,代表输入样例数。

接下来的每个样例:

第一行包含两个正整数N , V, (N <= 1000 , V <= 1000 )物品的数量和背包的大小。

第二行N个正整数代表每种物品的价值。

第三行N个正整数代表每种物品的大小,且与第二行的价值按顺序对应。

Output

每组样例一行,输出Teddy能带走的最大价值。

Sample Input

1 3 17 2 9 3 1 4 3

Sample Output

38