Given description of n items (weight and value) and a knapsack of capacity weight W, you have to calculate maximum value that you can get from these items without overflowing the weight of the knapsack. You cannot take any partial amount of item.
Input starts with an integer T (≤ 111), denoting the number of test cases.
Each case contains two integers n (1 ≤ n ≤ 42) and W (1 ≤ W ≤ 500000000) and the next n line will contain two integers A and B (0<=A,B<=20000000) separated by spaces representing the weight and value of each item respectively.
For each set of input, print the case number and the number of possible combinations.
| Input | Output |
|---|---|
1 5 100 2 3 200 5 55 6 99 1 23 1 | Case 1: 10 |
Take 1st, 3rd and 5th Item into the knapsack. So, total value you can get is 3+6+1=10 and it is the maximum.
This problem was authored for Inter Department Programming Contest 2016 at Jahangirnagar University and is being hosted on Toph per author's request.