Konstantin and Ilia live in the same house. Konstantin lives upstairs, and enjoys activities that involve jumping, moving furniture around, and  in general  making noise. Ilia lives downstairs, and enjoys sleep.
In order to have a good evening, Konstantin wants to do at least K activities. Last night, Ilia asked Konstantin to try not to wake him up; and because Konstantin is a very nice neighbor, he agreed. Unfortunately, he took Ilia's request a bit too literally, and he will choose his activities in such a way as to minimize the probability that Ilia is woken up after falling asleep.
Each possible activity for Konstantin has an associated probability a_{i}/b_{i}. If Konstantin performs this activity, then at the end of it, Ilia will be awake with probability a_{i}/b_{i}, and asleep otherwise, regardless of whether he was asleep at the start. Moreover, for each possible activity Konstantin can perform it at most c_{i} times (more than that would be boring, and Konstantin won't have a good evening if he's bored).
Konstantin wants to choose a number of activities to do, in order, so that:
What is the smallest Q Konstantin can achieve while having a good evening? Note that Konstantin cannot tell whether Ilia is awake or asleep, and so he cannot adapt his activities using that information.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a pair of integers, N, K, on a line by themselves. N lines follow, each of which represents an activity that Konstantin can choose. Each of those lines is formatted as "a_{i}/b_{i} c_{i}", indicating that there is an activity which would leave Ilia awake with probability a_{i}/b_{i} and which Konstantin can perform at most c_{i} times without being bored.
For each test case, output one line containing "Case #x: Q", where x is the case number (starting from 1) and Q is the smallest probability of Ilia waking up during the course of the activities that Konstantin performs. Answers with absolute or relative error no larger than 10^{6} will be accepted.
1 ≤ T ≤ 100.
0 ≤ a_{i} ≤ b_{i} ≤ 1000000 for all i.
1 ≤ b_{i} and 1 ≤ c_{i} for all i.
1 ≤ K ≤ the sum of all c_{i} in that test case.
1 ≤ N ≤ 100.
The sum of all c_{i} is no larger than 100 in each test case.
1 ≤ N ≤ 10000.
The sum of all c_{i} is no larger than 10^{6} in each test case.
Input 
Output 
3

Case #1: 0.000000000

Points  Correct  Attempted 

13pt  21  24 
17pt  16  21 