결정타

Khodislav는 D&D를 하고 있다. 지금 그의 캐릭터는 몬스터와 싸우고 있고, Khodislav는 자신의 공격을 이상하리만치 확신하며 마지막 결정타로 적을 끝장내려 한다. 캐릭터는 여러 무기를 가지고 있는데, 이 무기들이 줄 수 있는 피해는 주사위를 굴려 정해지며 세 수 $n$, $f$, $m$으로 나타낸다. 여기서 $n$은 주사위의 개수, $f$는 주사위의 면 수, $m$은 보정값이다. 예를 들어 $n = 3$, $f = 8$, $m = 5$라면 8면체 주사위 세 개를 굴려 나온 눈의 합에 5를 더해 피해를 정하며, 보통 $3d8 + 5$라고 쓴다.

몬스터를 끝장내려면 무기가 $D$ 이상의 피해를 줘야 한다. Khodislav가 몬스터를 죽일 확률이 최대가 되는 무기를 고르도록 도와주자.

주사위를 굴린 결과는 서로 독립이고, 주사위의 각 면이 나올 확률은 같다. 주사위의 각 면에는 $1$부터 $f$까지의 수가 하나씩 적혀 있다.

입력 파일의 첫째 줄에 정수 $T$가 주어진다. 이는 테스트의 수이다($1 \le T \le 5\,000$). 이어서 $T$개의 테스트가 주어진다.

테스트의 첫째 줄에는 두 정수 $W$와 $D$가 주어진다. $W$는 캐릭터가 가진 무기의 수, $D$는 몬스터를 끝장내는 데 필요한 최소 피해이다($1 \le W \le 5\,000$, $1 \le D \le 250$).

다음 $W$개 줄에 무기가 하나씩 주어진다. 각 줄에는 세 정수 $n$, $f$, $m$이 주어진다. $n$은 주사위의 개수, $f$는 주사위의 면 수, $m$은 보정값이다($1 \le n \le 10$, $2 \le f \le 20$, $-10 \le m \le 10$).

모든 테스트의 무기 수 합은 $5\,000$을 넘지 않는다.

각 테스트마다 한 번의 공격으로 $D$ 이상의 피해를 줄 최대 확률을 한 줄에 실수로 출력한다. 답의 절대 오차는 $10^{-11}$을 넘지 않아야 한다.