Dalam sebuah permainan aksi populer, terdapat $n$ peralatan serangan kritis berbeda yang tersedia di toko. Peralatan ke-$i$ memiliki peluang sebesar $\frac{p_i}{100}$ untuk memicu serangan kritis dengan pengali $v_i$, dan berharga $w_i$ koin. Setiap peralatan hanya dapat dibeli satu kali.

Ketika beberapa peralatan memicu serangan kritis secara bersamaan, hanya pengali tertinggi yang berlaku. Jika tidak ada peralatan yang memicu serangan kritis, pengali efektif dianggap bernilai $0$.

Anda dapat menghabiskan paling banyak $m$ koin untuk membeli beberapa peralatan. Anda perlu memaksimalkan nilai harapan pengali efektif dari peralatan yang Anda beli.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 300$), yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($1 \le n, m \le 3 \times 10^3$), yang menyatakan banyaknya peralatan dan jumlah koin maksimum yang dapat Anda habiskan.

Untuk $n$ baris berikutnya, baris ke-$i$ berisi tiga bilangan bulat $p_i$, $v_i$, dan $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), yang menyatakan peralatan ke-$i$.

Dijamin bahwa jumlah dari $n$ dan jumlah dari $m$ di seluruh kasus uji tidak melebihi $3 \times 10^3$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan riil tunggal, yang menyatakan nilai harapan maksimum dari pengali efektif.

Jawaban Anda akan dianggap benar jika galat absolut atau relatifnya tidak melebihi $10^{-6}$. Secara formal, misalkan jawaban Anda adalah $a$ dan jawaban juri adalah $b$, jawaban Anda diterima jika dan hanya jika $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Contoh

Contoh Masukan 1

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

Contoh Keluaran 1

68.750000000000
0.000000000000