Jegyek

Péter a félévi jegyeit nézegeti - valami nincs rendben velük. Javítania kellene néhány tárgyból, de az idő… Meg kell terveznie a javítást, melyikből próbálkozzon, milyen jegyre próbálkozzon javítani, mennyi időt szánjon rá egyáltalán.

A következőképpen gondolkozik: “Van $N$ tantárgyam, aktuális osztályzataimat is tudom ( $g_{1},\ldots,g_{N}$ ), van $T$ időegységem a felkészülésre, tudom hogy mennyi időre van szükségem ahhoz, hogy az $i$ .-ik tárgyból egyesről kettesre, kettesről hármasra, hármasról négyesre vagy négyesről ötösre javítsak ( $t_{i,1},t_{i,2},t_{i,3},t_{i,4}$ ). Természetesen, ha az $i$ . tárgyból mondjuk kettesről négyesre szeretnék javítani, akkor $t_{i,2}+t_{i,3}$ időre van szükségem a felkészüléshez. Megbukni semmiből sem akarok, így az egyeseket mindenképpen javítanom kell. Az adott $T$ keretein belül mi a legjobb átlag amit el tudok érni?”

Segítsünk neki megválaszolni a kérdést!

Példa:

N=2
aktuális jegyek: 1, 2
T=20
szükséges felkészülési idők:
1. tárgy: 8 8 9 10
2. tárgy: 2 3 4 5
Két lehetősége van:
- Az 1. tárgyból 2-esre javít, a többi időt a 2. tárgyra szánja.
    Összesen 8+(3+4+5) időegység, az átlag 3.5.
- Az 1. tárgyból 3-asra javít (jobbra nincs idő), a második tárgyból is 3-asra.
    Összesen (8+8)+3 időegység, az átlag 3.

Bemenet specifikáció

Az első sorban a tantárgyak $N$ száma, a következőben az aktuális jegyek $g_{1},\ldots,g_{N}$ listája van. A harmadik sor a redelkezésre álló $T$ időt, a következő $N$ sor pedig a javításokhoz szükséges $t_{i,1}\le \ldots \le t_{i,4}$ időket tartalmazza $i=1,\ldots ,N$ . A számok a sorokon belül üreshellyel vannak elválasztva.

Kimenet specifikáció

Ha lehetséges minden egyes osztályzatot legalább kettesre javítani, akkor az elérhető legjobb átlagot 2 jegyre kerekítve, egyébként a :-( sztringet írjuk egy sorba.