Grammy á tvo liðsfélaga, A og B. Venjulega fara liðsfélagarnir tveir út að borða á góðum veitingastöðum á hverjum degi, en Grammy borðar yfirleitt í mötuneyti skólans. Að borða í mötuneyti skólans sparar tíma og peninga, en að fara út að borða hefur stundum í för með sér leigubílakostnað. Engu að síður kemur fyrir að Grammy ákveður að fara út með liðsfélögum sínum til að gera vel við sig í mat.
Þegar líður að mánaðamótum á Grammy aðeins $m$ júan eftir fyrir framfærslu sinni og hún þarf að láta þessa peninga duga næstu $n$ daga. Á $i$-ta degi hefur hún um tvennt að velja:
- Borða í mötuneytinu, fá ánægju upp á $a_i$ og eyða $b_i$ júönum.
- Fara út að borða með liðsfélögum sínum, fá ánægju upp á $c_i$ og eyða $d_i$ júönum.
Þar sem A og B fara út að borða á hverjum degi fellur til leigubílakostnaður á hverjum degi. Látum $e_i$ vera leigubílagjaldið á $i$-ta degi; þau þrjú hafa sett sér reglu um greiðslu leigubílsins:
- Ef Grammy fer ekki út að borða á $i$-ta degi eru líkurnar $\frac{p_i}{100}$ á að A borgi leigubílinn og líkurnar $(1 - \frac{p_i}{100})$ á að B borgi.
- Ef Grammy fer út að borða á $i$-ta degi, og síðan Grammy borgaði síðast fyrir leigubílinn (eða frá fyrsta degi ef Grammy hefur aldrei borgað fyrir leigubílinn) hafa bæði A og B borgað fyrir leigubílinn að minnsta kosti einu sinni hvort (óháð því hvort Grammy fór út að borða í það skiptið), þá mun Grammy borga fyrir leigubílinn í þetta sinn. Annars borgar annar liðsfélaganna samkvæmt fyrri reglunni.
Á hverjum degi velur Grammy hvað hún gerir fyrir máltíðina. Hún veit hver borgaði leigubílinn daginn áður og markmið hennar er að hámarka væntigildi heildaránægjunnar, um leið og hún tryggir að heildarútgjöldin fari ekki yfir $m$ júan í versta falli. Ef hún tekur bestu mögulegu ákvarðanir á hverjum degi, hvert er þá væntigildi heildaránægjunnar?
Inntak
Það er aðeins eitt prófunartilvik í hverri prófunarskrá.
Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($1 \le n \le 2 \times 10^3$, $1 \le m \le 5 \times 10^3$), sem tákna fjölda daga og hámark heildarútgjalda.
Í næstu $n$ línum inniheldur $i$-ta línan sex heiltölur $a_i$, $b_i$, $c_i$, $d_i$, $e_i$ og $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$). Merking þeirra er lýst hér að ofan.
Úttak
Prentið eina línu sem inniheldur eina tölu sem táknar mesta mögulega væntigildi heildaránægju. Ef engin áætlun er til þar sem heildarútgjöldin verða minni en eða jöfn $m$ júönum í versta falli skal prenta $-1$.
Svarið þitt telst rétt ef algild eða hlutfallsleg skekkja þess fer ekki yfir $10^{-6}$. Formlega séð, ef úttakið þitt er $a$ og svar dómnefndar er $b$, þá er úttakið þitt samþykkt ef og aðeins ef $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Dæmi
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