QOJ.ac

QOJ

Memory Limit: 1024 MB Total points: 13

# 5945. Data Packing

Statistics

Problem

Adam, being a well-organized man, has always been keenly interested in organizing all his stuff. In particular, he fondly remembers the many hours of his youth that were spent moving files from his computer onto Compact Discs.

There were two very important rules involved in this procedure. First, in order to ensure that all discs could be labeled clearly, Adam would never place more than two files on the same disc. Second, he would never divide a single file over multiple discs. Happily, the discs he was using were always large enough to make this possible.

Thinking back, Adam is now wondering whether he arranged his files in the best way, or whether he ended up wasting some Compact Discs. He will provide you with the capacity of the discs he used (all his discs had the same capacity) as well as a list of the sizes of the files that he stored. Please help Adam out by determining the minimum number of discs needed to store all his files—following the two very important rules, of course.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers: the number of files to be stored N, and the capacity of the discs to be used X (in MBs). The next line contains the N integers representing the sizes of the files Si (in MBs), separated by single spaces.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of discs needed to store the given files.

Limits

Memory limit: 1 GB.

1 ≤ T ≤ 100.

1 ≤ X ≤ 700.

1 ≤ Si ≤ X.

Small dataset (5 Points)

Time limit: 60 10 seconds.

1 ≤ N ≤ 10.

Large dataset (8 Points)

Time limit: 120 20 seconds.

1 ≤ N ≤ 104

Sample

3
3 100
10 20 70
4 100
30 40 60 70
5 100
10 20 30 40 60
Case #1: 2
Case #2: 2
Case #3: 3