Problem F
Vinnuálag

Vitandi allt sem þú veist nú um ÁFLV hugsar þú með þér hversu mikið þú hefðir þurft að hafa fyrir áfanganum hefðir þú dreift álaginu jafnt yfir önnina? Það er einmitt það sem við munum skoða hér. Með jöfnu álagi er meint að jafn mörgum sekúndum sé varið í verkefni í hverri viku.

Í hverri viku voru sett fyrir verkefni, og þar sem önninni er lokið veistu nú hvað hvert verkefni tekur margar sekúndur að klára. Hvert verkefni gefur einhvern fjölda stiga, og hver vika er með einhvert gildi $s$ sem segir hvað maður þarf mörg stig til að fá $10$. Ef maður fær færri en $s$ stig reiknast einkunn sem $10(1-(1-x/s{)}^2)$ þar sem $x$ er fjöldi stiga sem fengust. Gerum einnig ráð fyrir að við gerum verkefnin í þeirri röð sem þau eru gefin. Hálfklárað verkefni gefur engin stig.

Þar að auki gilda aðeins $k$ bestu vikurnar af $n$ til einkunnar, og gildir hver að þessum vikum jafnt. Vikurnar gilda samtals $75\mathrm{\%}$ af einkunn, og próf $25\mathrm{\%}$ á móti. Til að vera örugg þá viljum við finna álagið sem lætur verkefnaeinkunn vera að minnsta kosti $4.75$, svo áfanganum sé náð ef prófi er náð.

Því er spurningin, hvað þarf margar sekúndur á viku til að ná áfanganum?

1 Inntak

Fyrsta lína inntaksins inniheldur heiltölur $n$ og $1\le k\le n$, fjölda vikna í áfanganum og fjölda vikna sem gilda til lokaeinkunnar. Næst fylgja $3n$ línur, hverjar þrjár lýsa einni viku. Fyrsta línan inniheldur tvær heiltölur $0\le s\le {10}^9$ og $m$, þar sem $s$ er fjöldi stiga sem þarf til að fá $10$ þá vikuna og $m$ er fjöldi verkefna í þeirri viku. Önnur línan inniheldur $m$ heiltölur $0\le t_i\le 10000$, fjöldi sekúndna sem þarf til að ljúka hverju verkefni. Þriðja línan inniheldur $m$ heiltölur $0\le s_i\le 10000$, fjöldi stiga sem fæst fyrir hvert verkefni. Gera má ráð fyrir að hægt sé að fá $10$ í hverri viku ef nægur tími er lagður í það. Heildarfjöldi verkefna verður mest ${10}^5$.

2 Úttak

Prenta skal lágmarksfjölda sekúndna sem þarf að verja í áfangann á viku til að forðast fall. Gefið er að svarið sé eins fyrir allar lokaeinkunnir í $[4.75-{10}^{-6},4.75+{10}^{-6}]$

Stigagjöf

3 2
10 3
5 5 5
5 5 5
4 2
20 20
2 2
8 2
8 8
4 4

8