Upstairs and Downstairs

Konstantin and Ilia live in the same house. Konstantin lives upstairs and likes activities that involve jumping, moving furniture around and generally making noise. Ilia lives downstairs and likes to sleep.

To have a good evening, Konstantin wants to perform at least $K$ activities. Last night Ilia asked him to try not to wake him up, and Konstantin, who is a good neighbor, agreed. He took the request very literally, so he picks his activities to make the probability that Ilia wakes up after falling asleep as small as possible.

Activity $i$ has a probability $a_i / b_i$ attached to it. When Konstantin performs it, Ilia is awake at the end of that activity with probability $a_i / b_i$ and asleep otherwise. This outcome does not depend on whether Ilia was asleep when the activity started, and it is independent of the outcome of every other activity. Konstantin can perform activity $i$ at most $c_i$ times, because doing it more often is boring, and a bored Konstantin does not have a good evening.

Konstantin fixes an ordered sequence of activities so that:

• the total number of activities is at least $K$;
• activity $i$ is performed no more than $c_i$ times;
• the probability $Q$ that Ilia is woken up one or more times is as small as possible.

Ilia starts awake, so waking him up means that he is asleep at the end of some activity and awake at the end of the next one.

Konstantin cannot tell whether Ilia is awake or asleep, so he decides the whole sequence in advance and never adapts it while the evening goes on.

Find the smallest $Q$ Konstantin can achieve while still having a good evening.

The first line contains the number of test cases $T$. Each test case begins with a line holding two integers $N$ and $K$. The next $N$ lines describe the activities Konstantin can choose from, one per line, in the format a/b c: the activity leaves Ilia awake with probability $a_i / b_i$, and Konstantin can perform it at most $c_i$ times. For example, 3/4 2 is an activity that leaves Ilia awake with probability $3/4$ and can be performed at most twice.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10^4$
• $0 \le a_i \le b_i \le 10^6$, $1 \le b_i$, $1 \le c_i$
• Let $S$ be the sum of all $c_i$ in one test case. Then $1 \le K \le S$ and $S \le 10^6$.

For each test case, print one line in the format Case #x: Q, where $x$ is the case number starting from 1 and $Q$ is the smallest probability that Ilia is woken up during the activities Konstantin performs.

Print $Q$ rounded to exactly nine digits after the decimal point. Every answer in the test data is far from a rounding boundary, so a double precision result printed with nine digits gives the expected line.