In un popolare gioco d'azione, ci sono $n$ diversi equipaggiamenti per il colpo critico disponibili nel negozio. L'$i$-esimo equipaggiamento ha una probabilità pari a $\frac{p_i}{100}$ di attivare un colpo critico con moltiplicatore $v_i$, e costa $w_i$ monete. Ogni equipaggiamento può essere acquistato una sola volta.

Quando più equipaggiamenti attivano colpi critici contemporaneamente, ha effetto solo il moltiplicatore più alto. Se nessun equipaggiamento attiva un colpo critico, il moltiplicatore effettivo è considerato pari a $0$.

Puoi spendere al massimo $m$ monete per acquistare alcuni equipaggiamenti. Devi massimizzare il valore atteso del moltiplicatore effettivo degli equipaggiamenti che hai acquistato.

Input

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 300$), che indica il numero di casi di test. Per ciascun caso di test:

La prima riga contiene due interi $n$ e $m$ ($1 \le n, m \le 3 \times 10^3$), che indicano il numero di equipaggiamenti e il numero massimo di monete che puoi spendere.

Per le successive $n$ righe, la $i$-esima riga contiene tre interi $p_i$, $v_i$ e $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), che indicano l'$i$-esimo equipaggiamento.

È garantito che la somma di $n$ e la somma di $m$ su tutti i casi di test non superano $3 \times 10^3$.

Output

Per ciascun caso di test, stampa una riga contenente un singolo numero reale, che indica il massimo moltiplicatore effettivo atteso.

La tua risposta sarà considerata corretta se il suo errore assoluto o relativo non supera $10^{-6}$. Formalmente, supponendo che la tua risposta sia $a$ e la risposta della giuria sia $b$, la tua risposta è accettata se e solo se $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Esempio

Input di esempio 1

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

Output di esempio 1

68.750000000000
0.000000000000