Dans un jeu d'action populaire, il y a $n$ équipements de coup critique différents disponibles dans la boutique. Le $i$-ème équipement a une probabilité de $\frac{p_i}{100}$ de déclencher un coup critique avec un multiplicateur $v_i$, et coûte $w_i$ pièces. Chaque équipement ne peut être acheté qu'une seule fois.

Lorsque plusieurs équipements déclenchent des coups critiques simultanément, seul le multiplicateur le plus élevé prend effet. Si aucun équipement ne déclenche de coup critique, le multiplicateur effectif est considéré comme étant $0$.

Vous pouvez dépenser au plus $m$ pièces pour acheter certains équipements. Vous devez maximiser l'espérance du multiplicateur effectif des équipements que vous avez achetés.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 300$), indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient deux entiers $n$ et $m$ ($1 \le n, m \le 3 \times 10^3$), indiquant le nombre d'équipements et le nombre maximum de pièces que vous pouvez dépenser.

Pour les $n$ lignes suivantes, la $i$-ème ligne contient trois entiers $p_i$, $v_i$ et $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), indiquant le $i$-ème équipement.

Il est garanti que la somme de $n$ et la somme de $m$ sur tous les cas de test ne dépassent pas $3 \times 10^3$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un seul nombre réel, indiquant l'espérance maximale du multiplicateur effectif.

Votre réponse sera considérée comme correcte si son erreur absolue ou relative ne dépasse pas $10^{-6}$. Formellement, supposons que votre réponse soit $a$ et que celle du jury soit $b$, votre réponse est acceptée si et seulement si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Exemple

Exemple d'entrée 1

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

Exemple de sortie 1

68.750000000000
0.000000000000