En un popular juego de acción, hay $n$ equipamientos diferentes de golpe crítico disponibles en la tienda. El $i$-ésimo equipamiento tiene una probabilidad de $\frac{p_i}{100}$ de activar un golpe crítico con multiplicador $v_i$, y cuesta $w_i$ monedas. Cada equipamiento se puede comprar solo una vez.

Cuando múltiples equipamientos activan golpes críticos simultáneamente, solo surte efecto el multiplicador más alto. Si ningún equipamiento activa un golpe crítico, el multiplicador efectivo se considera $0$.

Puedes gastar como máximo $m$ monedas para comprar algunos equipamientos. Debes maximizar el valor esperado del multiplicador efectivo de los equipamientos que compraste.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 300$), que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n, m \le 3 \times 10^3$), que indican el número de equipamientos y el número máximo de monedas que puedes gastar.

En las siguientes $n$ líneas, la $i$-ésima línea contiene tres enteros $p_i$, $v_i$ y $w_i$ ($1 \le p_i \le 100, 1 \le v_i \le 10^9, 1 \le w_i \le 3 \times 10^3$), que indican el $i$-ésimo equipamiento.

Se garantiza que la suma de $n$ y la suma de $m$ en todos los casos de prueba no superan $3 \times 10^3$.

Salida

Para cada caso de prueba, imprime una línea con un único número real, que indique el multiplicador efectivo esperado máximo.

Tu respuesta se considerará correcta si su error absoluto o relativo no supera $10^{-6}$. Formalmente, supongamos que tu respuesta es $a$ y la respuesta del jurado es $b$; tu respuesta se acepta si y solo si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Ejemplo

Entrada de ejemplo 1

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

Salida de ejemplo 1

68.750000000000
0.000000000000