I ett populärt actionspel finns det $n$ olika utrustningar för kritisk träff tillgängliga i butiken. Den $i$:te utrustningen har sannolikheten $\frac{p_i}{100}$ att utlösa en kritisk träff med multiplikatorn $v_i$, och kostar $w_i$ mynt. Varje utrustning kan endast köpas en gång.

När flera utrustningar utlöser kritiska träffar samtidigt är det bara den högsta multiplikatorn som gäller. Om ingen utrustning utlöser en kritisk träff betraktas den effektiva multiplikatorn som $0$.

Du kan spendera högst $m$ mynt för att köpa några utrustningar. Du ska maximera väntevärdet av den effektiva multiplikatorn för de utrustningar du köpt.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett heltal $T$ ($1 \le T \le 300$), som anger antalet testfall. För varje testfall:

Den första raden innehåller två heltal $n$ och $m$ ($1 \le n, m \le 3 \times 10^3$), som anger antalet utrustningar och det maximala antalet mynt du kan spendera.

För de följande $n$ raderna innehåller den $i$:te raden tre heltal $p_i$, $v_i$ och $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), som anger den $i$:te utrustningen.

Det garanteras att summan av $n$ och summan av $m$ över alla testfall inte överstiger $3 \times 10^3$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett enda reellt tal, vilket anger det maximala väntevärdet för den effektiva multiplikatorn.

Ditt svar betraktas som korrekt om dess absoluta eller relativa fel inte överstiger $10^{-6}$. Formellt sett, anta att ditt svar är $a$ och juryns svar är $b$; ditt svar accepteras om och endast om $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Exempel

Exempelindata 1

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

Exempelutdata 1

68.750000000000
0.000000000000