Grammy tiene dos compañeros de equipo, A y B. Normalmente, los dos compañeros salen a comer a buenos restaurantes todos los días, mientras que Grammy suele comer en la cafetería de la escuela. Comer en la cafetería de la escuela ahorra tiempo y dinero, mientras que salir a comer a veces implica gastos de taxi. Aun así, hay ocasiones en las que Grammy decide salir con sus compañeros para mejorar sus comidas.
A medida que se acerca el final del mes, a Grammy solo le quedan $m$ yuanes para sus gastos de manutención, y necesita pasar los próximos $n$ días con este dinero. En el $i$-ésimo día, tiene dos opciones:
- Comer en la cafetería, obteniendo una satisfacción de $a_i$ y gastando $b_i$ yuanes.
- Salir a comer con sus compañeros de equipo, obteniendo una satisfacción de $c_i$ y gastando $d_i$ yuanes.
Como A y B salen a comer todos los días, habrá gastos de taxi cada día. Sea $e_i$ la tarifa del taxi en el $i$-ésimo día; los tres han establecido una regla para pagar el taxi:
- Si Grammy no sale a comer en el $i$-ésimo día, entonces hay una probabilidad de $\frac{p_i}{100}$ de que A pague el taxi, y una probabilidad de $(1 - \frac{p_i}{100})$ de que pague B.
- Si Grammy sale a comer en el $i$-ésimo día, y desde la última vez que Grammy pagó el taxi (o desde el primer día, si Grammy nunca ha pagado el taxi), tanto A como B han pagado el taxi al menos una vez cada uno (independientemente de si Grammy salió a comer en ese momento), entonces Grammy pagará el taxi esta vez. De lo contrario, uno de los compañeros pagará según la regla anterior.
Cada día, Grammy elegirá su acción antes de la comida. Ella sabrá quién pagó el taxi el día anterior, y su objetivo es maximizar la satisfacción total esperada, asegurándose de que los gastos totales no superen los $m$ yuanes en el peor de los casos. Si toma decisiones óptimas todos los días, ¿cuál es el valor esperado de la satisfacción total?
Entrada
Solo hay un caso de prueba en cada archivo de prueba.
La primera línea contiene dos enteros $n$ y $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), que indican el número de días y el límite total de gastos.
En las siguientes $n$ líneas, la $i$-ésima línea contiene seis enteros $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ y $p_i$ ($0 \le b_i, d_i, e_i \le 5 \times 10^3$, $0 \le a_i, c_i \le 10^9$, $0 \le p_i \le 100$). Sus significados se describen arriba.
Salida
Imprime una línea con un único número, indicando el valor esperado máximo de la satisfacción total. Si no existe ningún plan en el que los gastos totales sean menores o iguales a $m$ yuanes en el peor de los casos, imprime $-1$.
Tu respuesta se considerará correcta si su error absoluto o relativo no supera $10^{-6}$. Formalmente, supongamos que tu salida es $a$ y la respuesta del jurado es $b$; tu salida será aceptada si y solo si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Ejemplos
2 10
6 4 15 8 10 50
5 2 13 5 8 50
20.000000000000
5 12
2 0 10 5 3 0
2 0 9 4 3 100
2 0 12 7 3 0
2 0 8 4 3 100
2 0 10 6 3 0
25.000000000000
6 20
1 2 3 10 1 69
5 1 12 2 2 23
0 4 2 3 5 41
6 1 6 9 0 84
1 1 14 9 5 98
3 2 13 2 4 43
35.771706880000
3 10
10 4 30 8 1 0
10 4 20 5 1 100
10 6 5 2 1 50
-1