In einem beliebten Actionspiel gibt es $n$ verschiedene Ausrüstungsgegenstände für kritische Treffer im Shop. Der $i$-te Ausrüstungsgegenstand hat eine Wahrscheinlichkeit von $\frac{p_i}{100}$, einen kritischen Treffer mit dem Multiplikator $v_i$ auszulösen, und kostet $w_i$ Münzen. Jeder Ausrüstungsgegenstand kann nur einmal gekauft werden.

Wenn mehrere Ausrüstungsgegenstände gleichzeitig kritische Treffer auslösen, wirkt nur der höchste Multiplikator. Wenn kein Ausrüstungsgegenstand einen kritischen Treffer auslöst, wird der effektive Multiplikator als $0$ betrachtet.

Sie können höchstens $m$ Münzen ausgeben, um einige Ausrüstungsgegenstände zu kaufen. Sie müssen den Erwartungswert des effektiven Multiplikators der gekauften Ausrüstungsgegenstände maximieren.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 300$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n, m \le 3 \times 10^3$), die die Anzahl der Ausrüstungsgegenstände und die maximale Anzahl an Münzen angeben, die Sie ausgeben können.

In den folgenden $n$ Zeilen enthält die $i$-te Zeile drei ganze Zahlen $p_i$, $v_i$ und $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), die den $i$-ten Ausrüstungsgegenstand beschreiben.

Es wird garantiert, dass die Summe von $n$ und die Summe von $m$ über alle Testfälle hinweg $3 \times 10^3$ nicht überschreiten.

Ausgabe

Geben Sie für jeden Testfall eine Zeile mit einer einzigen reellen Zahl aus, die den maximalen erwarteten effektiven Multiplikator angibt.

Ihre Antwort wird als korrekt gewertet, wenn ihr absoluter oder relativer Fehler $10^{-6}$ nicht überschreitet. Formal ausgedrückt: Angenommen, Ihre Antwort ist $a$ und die Antwort der Jury ist $b$, dann wird Ihre Antwort genau dann akzeptiert, wenn $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ gilt.

Beispiel

Beispieleingabe 1

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

Beispielausgabe 1

68.750000000000
0.000000000000