Upstairs and Downstairs

Konstantin and Ilia live in the same house. Konstantin lives upstairs and likes activities that involve jumping, moving furniture around and 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 not to wake him up, and Konstantin agreed. He took the request literally, so he picks his activities so that the probability of waking Ilia after Ilia has fallen asleep is as small as possible.

Activity $i$ has a probability $a_i / b_i$ attached to it. When Konstantin performs that activity, Ilia is awake at the moment it ends with probability $a_i / b_i$ and asleep otherwise. Ilia's state before the activity does not change this probability. Konstantin can perform activity $i$ at most $c_i$ times. Doing it more often bores him, and a bored Konstantin does not have a good evening.

Konstantin fixes the whole sequence of activities in advance, so that:

• the sequence holds at least $K$ activities;
• activity $i$ appears at most $c_i$ times;
• the probability $Q$ that Ilia is woken up at least once is as small as possible.

Ilia starts the evening awake. He is woken up when he is asleep at the moment one activity ends and awake at the moment the next activity ends. Konstantin cannot see whether Ilia is awake or asleep, so he cannot change the plan while the evening goes on.

Find the smallest $Q$ Konstantin can reach.

The first line holds the number of test cases $T$. Each test case starts with a line holding two integers $N$ and $K$. The next $N$ lines describe one activity each in the format a/b c: the activity leaves Ilia awake with probability $a/b$ at the moment it ends, and Konstantin can perform it at most $c$ times.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0 \le a_i \le b_i \le 1000000$
• $1 \le b_i$ and $1 \le c_i$ for every $i$
• The sum of all $c_i$ in one test case is at most $100$.
• $1 \le K \le$ the sum of all $c_i$ in that test case.

For each test case print one line in the format Case #x: Q, where $x$ is the test case number starting from 1 and $Q$ is the smallest probability that Ilia is woken up. Print $Q$ with exactly nine digits after the decimal point.

Every answer is a rational number, and no answer lies within $10^{-12}$ of a value halfway between two nine digit decimals, so rounding a double precision result gives the required digits.