Rigged Roulette

You are playing roulette in a casino. The wheel carries the 37 numbers 0 to 36, and each player puts money on the numbers of their choice. Once everyone has placed their bets the wheel is spun, and the ball finally settles on one number. A player who bet on that number gets back 36 times the amount of that bet, so the profit on it is 35 times the bet. Money placed on any other number is lost.

After losing all night you work out the trick. The ball always settles on a number that carries the smallest total amount of money. If several numbers tie for the smallest total, the ball settles on one of them uniformly at random.

You bet after every other player has finished. Your remaining budget is $B$, and you may bet on zero or more different numbers. Each of your bets is a positive integer and the amounts may differ from number to number, but their sum cannot exceed $B$. Maximize the expected profit.

The profit is 36 times the amount you put on the number the ball settles on, minus the total amount you bet. Betting nothing gives a profit of 0, so the answer is never negative.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains the remaining budget $B$ and the count $N$ of numbers the other players have bet on, separated by a space. The second line contains $N$ integers, where the $i$-th integer $X_i$ is the total amount the other players put on that number. These $N$ numbers are distinct, and nobody has bet on the remaining $37 - N$ numbers.

• $1 \le T \le 100$
• $1 \le N \le 37$
• $1 \le B \le 10^{12}$
• $1 \le X_i \le 10^{12}$

For each test case print one line holding Case #x: followed by the maximum expected profit, rounded to exactly 10 digits after the decimal point. $x$ is the test case number starting at 1. Pad with zeros when fewer digits are needed.

The exact answer is a rational number whose denominator is at most 37, so the rounded value is unique. The value can reach $3 \times 10^{13}$, which a double precision float cannot print correctly to 10 decimal places. Keep the numerator and the denominator as integers and shift the digits yourself when you print.

Suppose 34 numbers are empty, the other three carry 5, 6 and 7, and the budget is 34. Put 1 on each of the 34 empty numbers. All 34 then hold a total of 1, the ball has to settle on one of them, you get back 36, and the profit is $36 - 34 = 2$.

Suppose 33 numbers are empty, two numbers carry 1, two more carry 10, and the budget is 34. Put 1 on each of the 33 empty numbers. Now 35 numbers hold a total of 1, but only 33 of them carry your money. You get back 36 with probability $33/35$, so the expectation is $\frac{33}{35} \times 36 - 33$.