W popularnej grze akcji w sklepie dostępnych jest $n$ różnych przedmiotów dających szansę na cios krytyczny. $i$-ty przedmiot ma prawdopodobieństwo $\frac{p_i}{100}$ na wywołanie ciosu krytycznego z mnożnikiem $v_i$ i kosztuje $w_i$ monet. Każdy przedmiot można kupić tylko raz.

Gdy wiele przedmiotów jednocześnie wywoła cios krytyczny, działa tylko najwyższy mnożnik. Jeśli żaden przedmiot nie wywoła ciosu krytycznego, efektywny mnożnik uznaje się za równy $0$.

Możesz wydać co najwyżej $m$ monet na zakup wybranych przedmiotów. Musisz zmaksymalizować wartość oczekiwaną efektywnego mnożnika zakupionych przedmiotów.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 300$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 3 \times 10^3$), oznaczające liczbę przedmiotów oraz maksymalną liczbę monet, jaką możesz wydać.

W kolejnych $n$ wierszach $i$-ty wiersz zawiera trzy liczby całkowite $p_i$, $v_i$ oraz $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), opisujące $i$-ty przedmiot.

Gwarantowane jest, że suma $n$ oraz suma $m$ po wszystkich przypadkach testowych nie przekraczają $3 \times 10^3$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę rzeczywistą, oznaczającą maksymalną wartość oczekiwaną efektywnego mnożnika.

Twoja odpowiedź zostanie uznana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekroczy $10^{-6}$. Formalnie, zakładając, że Twoja odpowiedź to $a$, a odpowiedź jury to $b$, Twoja odpowiedź zostanie zaakceptowana wtedy i tylko wtedy, gdy $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Przykład

Przykładowe wejście 1

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

Przykładowe wyjście 1

68.750000000000
0.000000000000