Programming Contest Strategy

As you are a contestant participating in an ACM ICPC contest, your goal is to solve as many problems as you can within the competition duration with the least total time possible.

Let's suppose that you can, in advance, estimate the time (in minutes) that you will spend to solve each problem. Your task is to plan how to solve the contest problems with maximizing the number of solved problems while minimizing the total time. The total time is the sum of the submission times (in minutes) for each problem solved. The submission time for a problem is the elapsed time (in minutes) from the start of the contest till the submission of the solution. In your plan, at best you can assume that you can solve every problem at the first submission in the estimated time, so you do not have to worry about the penalty time. You can only work on 1 problem at any time (no parallel work).

Input Specification

The first line contains an integer T (1 ≤ T ≤ 20), which is the number of test cases. Each test case has 2 lines. The first line of each test case contains 2 integers: N (1 ≤ N ≤ 20) is the number of contest problems, and L (1 ≤ L ≤ 1 500) is the duration of the contest (time in minutes). Then the second line contains N integers indicating the estimated solution times for each contest problem.

Output Specification

For each test case, print out the case number, followed by your best result possible by printing 3 integers. The first value is the number of solved problems. The second value is the submission time for your last solved problem, and the third value is the total time. See the sample output for the exact format.

Sample Input

1. 2
2. 6 100
3. 15 23 41 12 15 20
4. 5 200
5. 23 45 35 49 28

download as text file

Output for Sample Input

1. Case 1: 5 85 228
2. Case 2: 5 180 471

download as text file

Explanation

For the first test case in the sample input, the contest has 6 problems (A–F), and the competition lasts for 100 minutes. The times that you will use for each problem are given in the second line, i.e., Problem A uses 15 minutes, Problem B uses 23 minutes, Problem C uses 41 minutes, and so on.

For the best score in this particular contest, you will solve 5 problems. The last problem that you can solve is submitted at 85 minutes, and you will have a total time of 228. You will not have time to solve problem C.