Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Knapsack Revisited

Limits: 3s, 512 MB

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

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.

Output

For each set of input, print the case number and the number of possible combinations.

Samples

InputOutput
1
5 100
2 3
200 5
55 6
99 1
23 1
Case 1: 10

Explanation

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.

Discussion
Submit

Login to submit