In a popular action game, there are $n$ different critical strike equipments available in the shop. The $i$-th equipment has a probability of $\frac{p_i}{100}$ to trigger a critical strike with multiplier $v_i$, and costs $w_i$ coins. Each equipment can be bought only once.

When multiple equipments trigger critical strikes simultaneously, only the highest multiplier takes effect. If no equipment triggers a critical strike, the effective multiplier is regarded as $0$.

You can spend at most $m$ coins to buy some equipments. You need to maximize the expected effective multiplier of the equipments you bought.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 300$), indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 3 \times 10^3$), indicating the number of equipments and the maximum number of coins you can spend.

For the following $n$ lines, the $i$-th line contains three integers $p_i$, $v_i$, and $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), indicating the $i$-th equipment.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $3 \times 10^3$.

Output

For each test case, output one line containing a single real number, indicating the maximum expected effective multiplier.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. Formally speaking, suppose that your answer is $a$ and the jury's answer is $b$, your answer is accepted if and only if $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Example

Sample Input 1

2
3 15
75 50 5
50 100 10
25 200 15
2 10
50 10 100
70 30 1000

Sample Output 1

68.750000000000
0.000000000000