Í vinsælum hasarleik eru $n$ mismunandi búnaðarhlutir fyrir þung högg fáanlegir í versluninni. $i$-ti búnaðurinn hefur líkurnar $\frac{p_i}{100}$ á að virkja þungt högg með margfaldaranum $v_i$, og kostar $w_i$ myntir. Hvern búnað er aðeins hægt að kaupa einu sinni.

Þegar margir búnaðarhlutir virkja þung högg samtímis tekur aðeins hæsti margfaldarinn gildi. Ef enginn búnaður virkjar þungt högg telst virki margfaldarinn vera $0$.

Þú getur eytt í mesta lagi $m$ myntum til að kaupa einhvern búnað. Þú þarft að hámarka væntigildi virka margfaldarans fyrir búnaðinn sem þú keyptir.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 300$), sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($1 \le n, m \le 3 \times 10^3$), sem gefa til kynna fjölda búnaðarhluta og hámarksfjölda mynta sem þú getur eytt.

Í næstu $n$ línum inniheldur $i$-ta línan þrjár heiltölur $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$), sem lýsa $i$-ta búnaðinum.

Það er tryggt að summa $n$ og summa $m$ yfir öll prófunartilvik fari ekki yfir $3 \times 10^3$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina rauntölu, sem gefur til kynna hámarks væntigildi virka margfaldarans.

Svarið þitt telst rétt ef algild eða hlutfallsleg skekkja þess fer ekki yfir $10^{-6}$. Formlega séð, gerum ráð fyrir að svarið þitt sé $a$ og svar dómnefndar sé $b$; svarið þitt er samþykkt ef og aðeins ef $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Dæmi

Dæmi um inntak 1

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

Dæmi um úttak 1

68.750000000000
0.000000000000