== include(page="template/taskheader" task_id="sao") ==

Dupa ce a intrat in noul joc: Sword Art Online, Kirito s-a decis sa isi masoare puterile in ultimul quest aparut. Initial, Kirito are un $HP$ (viata) si $K$ potiuni magice. El are de infruntat $N$ monstrii foarte puternici. Din moment ce acesti monstrii sunt bossi la fiecare nivel din joc, Kirito este obligat sa se lupte cu cei $N$ inamici in ordinea aparitiei lor (monstrul $1$, monstrul $2$, etc.). Pentru fiecare monstru Kirito stie cat $HP$ pierde pentru a il omora. In lupta cu monstrul $i$ pierde $damage{~i~} HP$. Kirito poate la un anumit moment sa foloseasca una din cele $K$ potiuni pentru a distruge un monstru fara sa piarda viata. Ajutati-l pe Kirito sa alegea pe ce monstrii sa foloseasca cele $K$ potiuni pentru a reusi sa omoare cat mai multi dintre inamicii sai (daca Kirito se bate cu un monstru si ajunge cu $HP$-ul $0$ sau mai putin atunci automat moare si nu mai poate continua).

Dupa ce a intrat in noul joc: $Sword Art Online$, Kirito s-a decis sa isi masoare puterile in ultimul quest aparut. Initial, Kirito are un $HP$ (viata) si $K$ potiuni magice. El are de infruntat $N$ monstrii foarte puternici. Din moment ce acesti monstrii sunt bossi la fiecare nivel din joc, Kirito este obligat sa se lupte cu cei $N$ inamici in ordinea aparitiei lor (monstrul $1$, monstrul $2$, etc.). Pentru fiecare monstru Kirito stie cat $HP$ pierde pentru a il omora. In lupta cu monstrul $i$ pierde $damage{~i~} HP$. Kirito poate la un anumit moment sa foloseasca una din cele $K$ potiuni pentru a distruge un monstru fara sa piarda viata. Ajutati-l pe Kirito sa aleaga pe ce monstrii sa foloseasca cele $K$ potiuni pentru a reusi sa omoare cat mai multi dintre inamicii sai (daca Kirito se bate cu un monstru si il bate numai daca are cel putin ataga $HP$ cat si-ar lua damage de la un monstru. Atunci cand ajunge cu $HP$-ul $0$ sau mai putin atunci automat moare si nu mai poate continua).

h2. Date de intrare

* $1 ≤ N ≤ 100.000$
* $1 ≤ HP ≤ 1.000.000.000$

* $1 ≤ damage{~i~} ≤ 1.000.000.000$

* $1 ≤ |damage{~i~}| ≤ 1.000.000.000$

* $1 ≤ K ≤ N$

* $Daca un monstru are damage negativ inseamna ca jucatorul castiga hp luptandu-se cu el, insa daca jucatorul are deja 0 sau mai putin atunci nu se va putea bate oricum cu acel monstru.$
* $Pentru 50% din punctaj 1 ≤ damage{~i~}$

h2. Exemplu