Grammylla on kaksi joukkuetoveria, A ja B. Tavallisesti nämä kaksi joukkuetoveria käyvät joka päivä syömässä hienoissa ravintoloissa, kun taas Grammy syö yleensä koulun ruokalassa. Koulun ruokalassa syöminen säästää aikaa ja rahaa, kun taas ulkona syömisestä aiheutuu joskus taksikuluja. Siitä huolimatta Grammy päättää toisinaan lähteä joukkuetovereidensa mukaan ulos syömään parantaakseen aterioitaan.
Kuukauden lopun lähestyessä Grammylla on enää $m$ juania jäljellä elinkustannuksiinsa, ja hänen on pärjättävä tällä rahalla seuraavat $n$ päivää. $i$:ntenä päivänä hänellä on kaksi vaihtoehtoa:
- Syödä ruokalassa, jolloin hän saa tyytyväisyyden $a_i$ ja käyttää $b_i$ juania.
- Lähteä ulos syömään joukkuetovereidensa kanssa, jolloin hän saa tyytyväisyyden $c_i$ ja käyttää $d_i$ juania.
Koska A ja B käyvät ulkona syömässä joka päivä, taksikuluja syntyy päivittäin. Olkoon $e_i$ taksimatkan hinta $i$:ntenä päivänä; kolmikko on sopinut seuraavan säännön taksin maksamisesta:
- Jos Grammy ei lähde ulos syömään $i$:ntenä päivänä, A maksaa taksin todennäköisyydellä $\frac{p_i}{100}$ ja B maksaa todennäköisyydellä $(1 - \frac{p_i}{100})$.
- Jos Grammy lähtee ulos syömään $i$:ntenä päivänä, ja sen jälkeen kun Grammy viimeksi maksoi taksin (tai ensimmäisestä päivästä lähtien, jos Grammy ei ole koskaan maksanut taksia), sekä A että B ovat kumpikin maksaneet taksin vähintään kerran (riippumatta siitä, oliko Grammy silloin mukana syömässä), tällä kertaa Grammy maksaa taksin. Muussa tapauksessa jompikumpi joukkuetovereista maksaa edellisen säännön mukaisesti.
Joka päivä Grammy valitsee toimintansa ennen ateriaa. Hän tietää, kuka maksoi taksin edellisenä päivänä, ja hänen tavoitteenaan on maksimoida kokonaistyytyväisyyden odotusarvo varmistaen samalla, että kokonaiskulut eivät pahimmassakaan tapauksessa ylitä $m$ juania. Jos hän tekee optimaalisia päätöksiä joka päivä, mikä on kokonaistyytyväisyyden odotusarvo?
Syöte
Jokaisessa testitiedostossa on vain yksi testitapaus.
Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), jotka ilmaisevat päivien lukumäärän ja kokonaiskulujen ylärajan.
Seuraavilla $n$ rivillä $i$:s rivi sisältää kuusi kokonaislukua $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ ja $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$). Niiden merkitykset on kuvattu yllä.
Tuloste
Tulosta yksi rivi, joka sisältää yhden luvun: kokonaistyytyväisyyden suurimman mahdollisen odotusarvon. Jos ei ole olemassa suunnitelmaa, jossa kokonaiskulut ovat pahimmassa tapauksessa enintään $m$ juania, tulosta $-1$.
Vastauksesi katsotaan oikeaksi, jos sen absoluuttinen tai suhteellinen virhe on enintään $10^{-6}$. Muodollisesti, jos tulosteesi on $a$ ja tuomariston vastaus on $b$, tulosteesi hyväksytään jos ja vain jos $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Esimerkit
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