Bạn đã chơi roulette trong một thời gian tại một sòng bạc địa phương. Roulette là một trò chơi sòng bạc đơn giản, trong đó nhiều người chơi đặt cược vào một hoặc nhiều số từ \(0\) đến \(36\) (bao gồm cả hai số này). Tiếp theo, một bánh xe được quay theo một hướng với một quả bóng quay theo hướng ngược lại. Bánh xe roulette chứa các số tương tự từ \(0\) đến \(36\). Một số bánh xe roulette thực tế cũng có một ô được gắn nhãn \(00\), nhưng bánh xe của chúng ta thì không. Cuối cùng, quả bóng rơi vào một trong các số. Nếu một người chơi đặt cược vào con số cụ thể đó, anh ta sẽ nhận được \(36\) lần số tiền đặt cược của mình (vì vậy lợi nhuận của lần đặt cược đó là \(35\) lần số tiền đặt cược). Tất cả các khoản đặt cược vào các con số khác đều thua.

Thật không may, may mắn đã không đứng về phía bạn và bạn đã thua suốt cả đêm. Tại một thời điểm, bạn bắt đầu tự hỏi liệu trò chơi roulette có công bằng hay không, và sau khi quan sát trò chơi thêm một chút, bạn nhận thấy một quy luật chắc chắn sẽ mang lại lợi nhuận cho sòng bạc: quả bóng luôn rơi vào một trong những con số có tổng số tiền đặt cược ít nhất! Nếu có nhiều số có cùng tổng số tiền đặt cược ít nhất, quả bóng sẽ rơi vào một trong những số đó một cách ngẫu nhiên đồng khả năng.

Tất nhiên, bạn sẽ thông báo cho các cơ quan chức năng về hành vi gian lận này, nhưng trước tiên bạn muốn gỡ lại tiền của mình bằng cách khai thác kiến thức mới tìm được. Để làm như vậy, bạn đợi cho đến khi tất cả những người chơi khác đã đặt cược xong và sau đó mới đặt cược của riêng mình. Thật không may, bạn chỉ còn lại một ngân sách hạn chế, vì vậy bạn không thể đặt cược nhiều hơn số đó. Bạn được phép đặt cược vào không hoặc nhiều số khác nhau và mỗi lần đặt cược đó có thể là bất kỳ số nguyên dương nào (có thể với số tiền khác nhau cho các số khác nhau), miễn là tổng số tiền đặt cược của bạn không vượt quá ngân sách của bạn. Lợi nhuận kỳ vọng tối đa bạn có thể kiếm được là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tuân theo.
Mỗi bộ test bao gồm hai dòng. Dòng đầu tiên chứa hai số nguyên: ngân sách bạn vẫn còn, \(B\), và số lượng số mà những người chơi khác đã đặt cược, \(N\). Dòng thứ hai chứa \(N\) số nguyên \(X_i\), tổng số tiền mà những người chơi khác đã đặt cược trên mỗi số khác nhau đó.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: " theo sau là lợi nhuận kỳ vọng tối đa mà bạn kiếm được nếu bạn đặt cược một cách tối ưu. Lợi nhuận sẽ được coi là chính xác nếu nó nằm trong sai số tuyệt đối hoặc tương đối là \(10^{-6}\) so với đáp án chính xác.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N \le 37\).

Phân nhóm

• Phân nhóm 1 (Visible): \(1 \le B, X_i \le 1,000\).
• Phân nhóm 2 (Hidden): \(1 \le B, X_i \le 10^{12}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
100 1
10
34 3
5 6 7
34 4
1 1 10 10

Case #1: 0
Case #2: 2
Case #3: 0.9428571429

Nguồn

Google Code Jam 2013, Vòng 3, bài Cheaters.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.