Fişierul intrare/ieşire:	sao.in, sao.out	Sursă	Algoritmiada 2015 Runda Finala
Autor	Eugenie Daniel Posdarascu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sword Art Online

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).

Date de intrare

Fişierul de intrare sao.in va contine pe prima linie 3 numere naturale N, K si HP. Pe linia 2 vor fi N elemente, elementul i reprezentand valoarea damage_i

Date de ieşire

Fişierul de ieşire sao.out va contine un singul numar natural reprezentand numarul maxim de monstrii pe care poate Kirito sa ii omoare

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ HP ≤ 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

Exemplu

Cum se trimit solutii?