Grammy hat zwei Teamkollegen A und B. Normalerweise gehen die beiden Teamkollegen jeden Tag in guten Restaurants essen, während Grammy meistens in der Schulmensa isst. In der Schulmensa zu essen spart Zeit und Geld, wohingegen das Auswärtsessen manchmal Taxikosten verursacht. Trotzdem gibt es Tage, an denen Grammy sich entscheidet, mit ihren Teamkollegen essen zu gehen, um sich eine bessere Mahlzeit zu gönnen.
Als das Monatsende näher rückt, hat Grammy nur noch $m$ Yuan für ihren Lebensunterhalt übrig, und sie muss mit diesem Geld über die nächsten $n$ Tage kommen. Am $i$-ten Tag hat sie zwei Möglichkeiten:
- In der Mensa essen, wodurch sie eine Zufriedenheit von $a_i$ erhält und $b_i$ Yuan ausgibt.
- Mit ihren Teamkollegen auswärts essen gehen, wodurch sie eine Zufriedenheit von $c_i$ erhält und $d_i$ Yuan ausgibt.
Da A und B jeden Tag auswärts essen gehen, fallen jeden Tag Taxikosten an. Sei $e_i$ der Taxifahrpreis am $i$-ten Tag; die drei haben folgende Regel für das Bezahlen des Taxis aufgestellt:
- Wenn Grammy am $i$-ten Tag nicht auswärts essen geht, bezahlt A mit einer Wahrscheinlichkeit von $\frac{p_i}{100}$ das Taxi, und B bezahlt mit einer Wahrscheinlichkeit von $(1 - \frac{p_i}{100})$.
- Wenn Grammy am $i$-ten Tag auswärts essen geht und seit dem letzten Mal, als Grammy das Taxi bezahlt hat (oder seit dem ersten Tag, falls Grammy noch nie das Taxi bezahlt hat), sowohl A als auch B jeweils mindestens einmal das Taxi bezahlt haben (unabhängig davon, ob Grammy zu diesem Zeitpunkt mitgegangen ist), dann muss Grammy diesmal das Taxi bezahlen. Andernfalls bezahlt einer der Teamkollegen gemäß der vorherigen Regel.
Jeden Tag wählt Grammy ihre Aktion vor dem Essen. Sie weiß, wer am Vortag das Taxi bezahlt hat, und ihr Ziel ist es, den Erwartungswert der Gesamtzufriedenheit zu maximieren und gleichzeitig sicherzustellen, dass die Gesamtausgaben im schlimmsten Fall $m$ Yuan nicht überschreiten. Wenn sie jeden Tag optimale Entscheidungen trifft, wie groß ist dann der Erwartungswert der Gesamtzufriedenheit?
Eingabe
In jeder Testdatei gibt es nur einen einzigen Testfall.
Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), die die Anzahl der Tage und das Gesamtausgabenlimit angeben.
In den folgenden $n$ Zeilen enthält die $i$-te Zeile sechs ganze Zahlen $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ und $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$). Ihre Bedeutungen sind oben beschrieben.
Ausgabe
Gib eine Zeile mit einer einzigen Zahl aus, die den maximalen Erwartungswert der Gesamtzufriedenheit angibt. Falls kein Plan existiert, bei dem die Gesamtausgaben im schlimmsten Fall höchstens $m$ Yuan betragen, gib $-1$ aus.
Deine Antwort wird als korrekt gewertet, wenn ihr absoluter oder relativer Fehler $10^{-6}$ nicht überschreitet. Formal ausgedrückt: Sei $a$ deine Ausgabe und $b$ die Antwort der Jury, dann wird deine Ausgabe genau dann akzeptiert, wenn $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ gilt.
Beispiele
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