{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThere is a lottery going to happen among $N$ groups of people. Group $i$ consists of $a_i$ persons. In the end, at most $M$ persons will be the winner of this lottery.\u003cbr\u003eThere is one extra restriction for this lottery: for each group, either all or none of the person in this group\u003cbr\u003eare winners. In other words, no partial winners allowed for each group.\u003cbr\u003eA lottery program is defined as a set of outcomes. The outcome announces the winners of the lottery. Each outcome has it’s own probability to happen, and the sum of probabilities among all outcomes equals to 1.0.\u003cbr\u003eA fair lottery program is a lottery program that makes each person having the same probability $p$ of winning the lottery. Find the maximum probability $p$ over all fair lottery programs.\u003cbr\u003eFor example, suppose there are 3 groups: $A$, $B$, and $C$, each consists of 1, 2, and 2 persons. At most 3 persons will be the winner of the lottery.\u003cbr\u003eOne possible fair lottery program is: it consists of only one outcome that no one wins. So each person has the same probability of 0% winning the lottery.\u003cbr\u003eA better fair lottery program is: there are two outcomes, each happening with probability of 50%. Outcome 1 announces person in group A and B as winners; and outcome 2 announces person in group C as winners.\u003cbr\u003eHence each person having the winning probability of 50%. It’s easy to verify that 50% is the maximum probability over all lottery programs.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, $T$. $T$ test cases follow.\u003cbr\u003eEach test case contains 2 lines, the first line consists of 2 numbers $N$, $M$ indicating the number of groups and the max number of lottery winners.\u003cbr\u003eThe second line consists of $N$ numbers $a_1, a_2, . . . , a_N$ indicating the number of persons in each group.\u003cbr\u003e$1 \\leq T \\leq 100$\u003cbr\u003e$1 \\leq N \\leq 10$\u003cbr\u003e$1 \\leq M \\leq 100$\u003cbr\u003e$1 \\leq a_i \\leq 100$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the maximum probability $p$ for each one to be the winner over all fair lottery programs. $y$ will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 3\r\n1 2 2\r\n4 2\r\n1 1 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 0.5000000000\r\nCase #2: 0.4000000000\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eThe first test case is the sample in the problem.\u003cbr\u003eIn the second test case, the best lottery program is: Assume groups are A(1), B(1), C(1), D(2), For [0, 0.2) persons in A, B are the winners. \u003cbr\u003eFor [0.2, 0.4) persons in B, C are the winners. For [0.4, 0.6) persons in A, C are the winners. For [0.6, 1) persons in D are the winners.\u003cbr\u003e"}}]}