Description

One day, you made a female friend.

You plan to spend $k$ days with her. Each day there are many types of activities to choose from, and you must choose exactly one to do that day (only one activity per day), such as going to the movies, going to a theme park, going shopping, and so on, for a total of $n$ activities. Of course, repeating the same activity too many times will feel boring to you, so the $i$-th activity can be done at most $c_i$ times.

Although you have a high IQ, your EQ leaves much to be desired. Even though these activities are meant to make her happy, your awkward words and overly rational behavior may cause mishaps. After careful calculation, you find that if on some day you do the $i$-th activity, she should be happy if everything goes well, but there is a certain probability that she will be unhappy. If she would otherwise be happy but you make her unhappy today, she will feel very let down, and her favorable impression of you will drop sharply. You want to avoid this as much as possible, so you must schedule which activity to do each of the $k$ days to minimize the expected number of times she feels let down.

She cares a lot about you, so her mood changes only because of you. Before day 1, since you have not invited her to do any activity, she is unhappy.

Input Format

The first line contains a non-negative integer $t$, the number of test cases.

For each test case, the first line contains two non-negative integers $n, k$, representing the number of activities you prepared and the number of days you will spend with her. $(1 \le n \le 10^5, 1 \le k \le 10^9)$

Then follow $n$ lines, each describing one activity, in the form x/y c, where all three numbers are non-negative integers. It means that after doing this activity, she will be unhappy with probability $\dfrac{x_i}{y_i}$, and this activity can be done at most $c_i$ times. $(x_i, y_i \le 10^4, c_i \le 10^9)$

Output Format

Output $t$ lines. For each test case, print the minimal expected number of times she feels let down, rounded to 6 decimal places.

3
1 2
0/1 3
1 2
1/1 3
1 2
1/2 3

0.000000
0.000000
0.250000

Hint

[Sample Explanation]

Consider the third test case. Since there is only one activity, you have to schedule it every day.

Before day 1 she is always unhappy. There are four cases: unhappy on day 1 and unhappy on day 2, happy on day 1 and unhappy on day 2, unhappy on day 1 and happy on day 2, happy on day 1 and happy on day 2. These four cases are equally likely because the activity makes her happy or unhappy each day with probability $50\%$.

Only in the second case does she feel let down once.

Therefore the answer is $\dfrac{0+1+0+0}{4}=0.25$.

[Constraints and Conventions]

For the first 10% of the testdata, $n, k \le 5$.

For the first 30% of the testdata, $n, k \le 7$.

For the first 40% of the testdata, $n, k \le 10$.

For the first 60% of the testdata, $n \le 10^3, k \le 10^5$.

For 100% of the testdata, $1 \le n \le 10^5, 1 \le k \le 10^9, 1 \le t \le 10$. The testdata guarantees the fractions are meaningful and $\sum\limits_{i=1}^n c_i \ge k$.

Translated by ChatGPT 5