Grammy ma dwóch kolegów z drużyny, A oraz B. Zazwyczaj ci dwaj koledzy codziennie chodzą jeść do dobrych restauracji, podczas gdy Grammy jada przeważnie w szkolnej stołówce. Jedzenie w szkolnej stołówce oszczędza czas i pieniądze, natomiast wyjście na miasto wiąże się czasem z kosztami taksówki. Mimo to zdarza się, że Grammy postanawia wyjść z kolegami z drużyny, aby zjeść lepszy posiłek.
Zbliża się koniec miesiąca i Grammy zostało już tylko $m$ juanów na utrzymanie, za które musi przeżyć kolejne $n$ dni. W $i$-tym dniu ma do wyboru dwie opcje:
- Zjeść w stołówce, zyskując satysfakcję $a_i$ i wydając $b_i$ juanów.
- Wyjść na posiłek z kolegami z drużyny, zyskując satysfakcję $c_i$ i wydając $d_i$ juanów.
Ponieważ A i B wychodzą na posiłek każdego dnia, codziennie pojawiają się koszty taksówki. Niech $e_i$ oznacza koszt taksówki w $i$-tym dniu; cała trójka ustaliła następującą zasadę płacenia za taksówkę:
- Jeśli Grammy nie wychodzi jeść w $i$-tym dniu, to z prawdopodobieństwem $\frac{p_i}{100}$ za taksówkę zapłaci A, a z prawdopodobieństwem $(1 - \frac{p_i}{100})$ zapłaci B.
- Jeśli Grammy wychodzi jeść w $i$-tym dniu, a od ostatniego razu, gdy Grammy płaciła za taksówkę (lub od pierwszego dnia, jeśli Grammy nigdy jeszcze nie płaciła za taksówkę), zarówno A, jak i B zapłacili za taksówkę co najmniej po jednym razie (niezależnie od tego, czy Grammy wówczas wychodziła z nimi jeść), to tym razem za taksówkę płaci Grammy. W przeciwnym razie zapłaci jeden z kolegów zgodnie z poprzednią zasadą.
Każdego dnia Grammy wybiera swoją decyzję przed posiłkiem. Wie, kto zapłacił za taksówkę poprzedniego dnia, a jej celem jest zmaksymalizowanie wartości oczekiwanej łącznej satysfakcji, przy jednoczesnym zagwarantowaniu, że w najgorszym przypadku łączne wydatki nie przekroczą $m$ juanów. Jaka jest wartość oczekiwana łącznej satysfakcji, jeśli każdego dnia podejmuje ona optymalne decyzje?
Wejście
W każdym pliku testowym znajduje się tylko jeden przypadek testowy.
Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), oznaczające liczbę dni oraz limit łącznych wydatków.
W kolejnych $n$ wierszach $i$-ty wiersz zawiera sześć liczb całkowitych $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ oraz $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$). Ich znaczenie opisano powyżej.
Wyjście
Wypisz jeden wiersz zawierający jedną liczbę, oznaczającą maksymalną wartość oczekiwaną łącznej satysfakcji. Jeśli nie istnieje plan, w którym łączne wydatki w najgorszym przypadku są mniejsze lub równe $m$ juanom, wypisz $-1$.
Twoja odpowiedź zostanie uznana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekroczy $10^{-6}$. Formalnie, niech Twoja odpowiedź wynosi $a$, a odpowiedź jury wynosi $b$; Twoja odpowiedź zostanie zaakceptowana wtedy i tylko wtedy, gdy $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Przykład
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