Sheldon is at Stuart's comic book store. He wants to buy those comics which aren't part of his collection. After browsing all the comics, he has found that there are N comics which he wants to buy. Since, he is limited on cash and has only C units of cash to spend, he wants to buy a subset of these N comics such that their total cost doesn't exceed C units and happiness he gets after buying those comics is maximum.
Each of N comics has some cost and happiness associated with it.
Since, Sheldon has gone extremely emotional after seeing so many comics and doesn't want to think about anything else, he has given you this task.
Note: It is also possible that he doesn't buy any comic. In that case, happiness will be 0.
Input Format:
First line contains T, number of test cases.
First line of each test case contains N and C, number of comics and cash to be spent respectively.
Second line of each test case contains N integers such that ith of those denote the cost of ith comic.
Third line of each test case contains N integers such that ith of those denote the happiness gained by ith comic.
Output Format:
For each test case, print the required answer in separate lines.
Constraints:
1≤T≤10
1≤N≤32
1≤C≤109
1≤costi≤109
1≤happinessi≤109
For first case, one way to get maximum happiness is to buy all 5 comics and total happiness will be 18 and cost will be 17 which fulfills the cost condition.
For second case, a happiness of 14 can be achieved by 1st, 3rd and 5th comic with a total cost 8. We can see that there is no way to achieve a larger happiness with cost within 10 units. Hence, 14 is the answer.
