I et populært actionspill er det $n$ forskjellige utstyr for kritisk treff tilgjengelig i butikken. Det $i$-te utstyret har en sannsynlighet på $\frac{p_i}{100}$ for å utløse et kritisk treff med multiplikator $v_i$, og koster $w_i$ mynter. Hvert utstyr kan bare kjøpes én gang.

Når flere utstyr utløser kritiske treff samtidig, er det bare den høyeste multiplikatoren som trer i kraft. Hvis ikke noe utstyr utløser et kritisk treff, regnes den effektive multiplikatoren som $0$.

Du kan bruke høyst $m$ mynter for å kjøpe noe utstyr. Du må maksimere forventningsverdien til den effektive multiplikatoren for utstyret du har kjøpt.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 300$), som angir antallet testtilfeller. For hvert testtilfelle:

Den første linjen inneholder to heltall $n$ og $m$ ($1 \le n, m \le 3 \times 10^3$), som angir antallet utstyr og det maksimale antallet mynter du kan bruke.

For de følgende $n$ linjene inneholder den $i$-te linjen tre heltall $p_i$, $v_i$ og $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), som angir det $i$-te utstyret.

Det er garantert at summen av $n$ og summen av $m$ over alle testtilfeller ikke overstiger $3 \times 10^3$.

Utdata

For hvert testtilfelle, skriv ut én linje som inneholder ett enkelt reelt tall, som angir den maksimale forventede effektive multiplikatoren.

Svaret ditt vil bli regnet som riktig hvis den absolutte eller relative feilen ikke overstiger $10^{-6}$. Formelt sett, anta at svaret ditt er $a$ og juryens svar er $b$; svaret ditt godtas hvis og bare hvis $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Eksempel

Eksempelinndata 1

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

Eksempelutdata 1

68.750000000000
0.000000000000