시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 0 0 0 0.000%

문제

Khodislav is playing D&D. At the moment, his character is fighting a monster and Khodislav, who is for some reason very sure in his attack, wants to destroy the enemy with the last crushing blow. His character has different weapons; the damage these weapons can cause is defined by rolling dice and characterized by three numbers $n$, $f$, and $m$, where $n$ is the number of dice, $f$ is the number of faces on each die, and $m$ is a modifier. For instance, if $n = 3$, $f = 8$, $m = 5$, then you will need to roll three eight-faced dice, sum the results, and add five to the sum to define the damage; this is usually written as $3d8 + 5$.

To destroy the monster, a weapon must inflict damage of $D$ or greater. Help Khodislav to choose a weapon for his character that will help him to kill the monster with maximum probability.

Dice rolls are independent; it is equally likely to roll each of the faces on a die. There are all numbers from $1$ to $f$ written on the faces of the die.

입력

In the first line of the input file, there is a single integer $T$ --- the number of tests ($1 \le T \le 5\,000$). It is followed by the description of $T$ tests.

The first line of a test contains two integers: $W$ --- the number of character's weapons and $D$ --- the minimum required damage to the monster ($1 \le W \le 5\,000$, $1 \le D \le 250$).

The following $W$ lines describe the weapons. Each line contains three integers: $n$ --- the number of the dice, $f$ --- the number of faces on each die, and $m$ --- the modifier ($1 \le n \le 10$, $2 \le f \le 20$, $-10 \le m \le 10$).

It is guaranteed that the total number of weapons in all tests is not greater than $5\,000$.

출력

For each test, print a single real number on a separate line --- the maximum probability of inflicting damage no less than $D$ with a single blow. The absolute error of the answers must not exceed $10^{-11}$.

예제 입력 1

2
2 2
1 20 -3
2 2 0
1 11
1 20 -10

예제 출력 1

1
0

예제 입력 2

3
1 6
1 6 0
1 7
2 6 0
1 100
10 20 10

예제 출력 2

0.166666666666667
0.583333333333333
0.799600378342187