Suositussa toimintapelissä kaupassa on saatavilla $n$ erilaista kriittisen osuman varustetta. $i$:nnellä varusteella on todennäköisyys $\frac{p_i}{100}$ laukaista kriittinen osuma kertoimella $v_i$, ja se maksaa $w_i$ kolikkoa. Jokaisen varusteen voi ostaa vain kerran.

Kun useat varusteet laukaisevat kriittisen osuman samanaikaisesti, vain suurin kerroin tulee voimaan. Jos mikään varuste ei laukaise kriittistä osumaa, vaikuttavaksi kertoimeksi katsotaan $0$.

Voit käyttää enintään $m$ kolikkoa ostaaksesi joitakin varusteita. Sinun tulee maksimoida ostamiesi varusteiden vaikuttavan kertoimen odotusarvo.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 300$), joka ilmaisee testitapausten lukumäärän. Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n, m \le 3 \times 10^3$), jotka ilmaisevat varusteiden lukumäärän ja enimmäismäärän kolikoita, jonka voit käyttää.

Seuraavilla $n$ rivillä $i$:s rivi sisältää kolme kokonaislukua $p_i$, $v_i$ ja $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), jotka kuvaavat $i$:nnen varusteen.

On taattu, että lukujen $n$ summa ja lukujen $m$ summa yli kaikkien testitapausten eivät ylitä arvoa $3 \times 10^3$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää yhden reaaliluvun: suurimman mahdollisen vaikuttavan kertoimen odotusarvon.

Vastauksesi katsotaan oikeaksi, jos sen absoluuttinen tai suhteellinen virhe on enintään $10^{-6}$. Muodollisesti, oletetaan että vastauksesi on $a$ ja tuomariston vastaus on $b$; vastauksesi hyväksytään jos ja vain jos $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Esimerkki

Esimerkkisyöte 1

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

Esimerkkituloste 1

68.750000000000
0.000000000000