Grammy a deux coéquipiers A et B. D'habitude, ses deux coéquipiers sortent manger dans de bons restaurants tous les jours, tandis que Grammy mange généralement à la cafétéria de l'école. Manger à la cafétéria de l'école permet d'économiser du temps et de l'argent, alors que sortir entraîne parfois des frais de taxi. Malgré cela, il arrive que Grammy choisisse de sortir avec ses coéquipiers pour améliorer ses repas.
À l'approche de la fin du mois, il ne reste plus à Grammy que $m$ yuans pour ses dépenses courantes, et elle doit tenir les $n$ prochains jours avec cet argent. Le $i$-ème jour, elle a deux choix :
- Manger à la cafétéria, ce qui lui procure une satisfaction de $a_i$ et lui coûte $b_i$ yuans.
- Sortir manger avec ses coéquipiers, ce qui lui procure une satisfaction de $c_i$ et lui coûte $d_i$ yuans.
Comme A et B sortent manger tous les jours, il y a des frais de taxi chaque jour. Soit $e_i$ le prix du taxi le $i$-ème jour ; tous les trois ont établi une règle pour payer la course de taxi :
- Si Grammy ne sort pas manger le $i$-ème jour, alors il y a une probabilité $\frac{p_i}{100}$ que A paie le taxi, et une probabilité $(1 - \frac{p_i}{100})$ que B paie.
- Si Grammy sort manger le $i$-ème jour, et que depuis la dernière fois où Grammy a payé le taxi (ou depuis le premier jour si Grammy n'a jamais payé le taxi), A et B ont chacun payé le taxi au moins une fois (que Grammy soit sortie manger ou non à ce moment-là), alors c'est Grammy qui paie le taxi cette fois-ci. Sinon, l'un des coéquipiers paiera selon la règle précédente.
Chaque jour, Grammy choisit son action avant le repas. Elle sait qui a payé le taxi la veille, et son objectif est de maximiser l'espérance de la satisfaction totale, tout en s'assurant que le total des dépenses ne dépasse pas $m$ yuans dans le pire des cas. Si elle prend des décisions optimales chaque jour, quelle est l'espérance de la satisfaction totale ?
Entrée
Il n'y a qu'un seul cas de test dans chaque fichier de test.
La première ligne contient deux entiers $n$ et $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), indiquant le nombre de jours et la limite totale de dépenses.
Pour les $n$ lignes suivantes, la $i$-ème ligne contient six entiers $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ et $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$). Leurs significations sont décrites ci-dessus.
Sortie
Affichez une ligne contenant un seul nombre, indiquant l'espérance maximale de la satisfaction totale. S'il n'existe aucun plan permettant de garantir que les dépenses totales seront inférieures ou égales à $m$ yuans dans le pire des cas, affichez $-1$.
Votre réponse sera considérée comme correcte si son erreur absolue ou relative ne dépasse pas $10^{-6}$. Formellement, en supposant que votre sortie soit $a$ et que la réponse du jury soit $b$, votre sortie est acceptée si et seulement si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Exemples
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