Rigged Roulette

Roulette is a casino game in which players bet money on one or more of the numbers 0 to 36. The wheel spins one way, a ball spins the other way, and the ball finally drops on one of the numbers 0 to 36. Some real wheels also have a slot marked 00, but this one does not. A player who bet on the number the ball drops on receives 36 times that bet, so the profit on that bet is 35 times the bet. Every bet placed on another number is lost.

You have lost money all night. After watching the game for a while you found the pattern that keeps the casino ahead: the ball always drops on a number that has the smallest total amount of money bet on it. When several numbers tie for the smallest total, the ball drops on one of them uniformly at random.

You wait until every other player has placed their bets, then place yours. Your remaining budget is $B$, and the sum of your bets cannot exceed it. You may bet on zero or more different numbers, and each of those bets is any positive integer amount, possibly different for different numbers. Find the largest expected profit you can make.

The first line contains the number of test cases $T$. $T$ test cases follow, each on two lines. The first line contains the budget you still have, $B$, and the number of numbers the other players bet on, $N$. The second line contains $N$ integers $X_1, X_2, \dots, X_N$, the total amount of money the other players bet on each of those different numbers.

Constraints

• $1 \le T \le 100$
• $1 \le N \le 37$
• $1 \le B, X_i \le 1000$

For each test case, print one line holding "Case #x: " followed by the largest expected profit, where $x$ is the test case number starting from 1. Round the profit to six digits after the decimal point and always print all six digits, padding with zeros when the value is an integer.

In the second test case of the first sample, bet 1 on each of the 34 numbers nobody bet on. That costs 34, and whichever number comes up you receive 36, so the profit is $36 - 34 = 2$.

In the third test case, bet 1 on each of the 33 numbers nobody bet on. Then 35 numbers hold a total of 1, and 33 of them are yours, so you receive 36 with probability $\frac{33}{35}$. The expected profit is $\frac{33}{35} \times 36 - 33 = \frac{33}{35}$, which rounds to 0.942857.