Fişierul intrare/ieşire: | sao.in, sao.out | Sursă | ad-hoc |
Autor | Andreescu Mihai, Barbalau Antonio | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 500 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Sword Art Online
Kirito se află în faţa provocării vieţii sale: este blocat într-o lume virtuală din care poate scăpa doar învingănd cei N monştri care apără drumul către ieşire. Pentru a o impresiona pe Asuna, el vrea să fie capabil să-i înfrunte pe toţi fără oprire. Pentru a face asta, el trebuie să îşi aleagă o armură şi o sabie. Deoarece economiseşte bani ca să-i facă un cadou frumos Asunei, a decis să analizeze M promoţii de forma: primeşti o armură de rezistenţă R şi o sabie de putere P care costă C lei. El nu poate cumula ofertele.
La început, va alege cea mai ieftină ofertă care l-ar face capabil să-i înfrângă pe monştri. După fiecare luptă, puterea sa de atac scade cu valoarea armurii monstrului, iar rezistenţa armurii sale scade cu puterea sabiei monstrului. Pentru a câştiga, atât armura, cât şi sabia lui Kirito trebuie să rămână intacte (rezistenţa, respectiv puterea lor trebuie să fie cel puţin zero).
Cerinţă
Se cere să se scrie un program care să citească monştrii şi ofertele pe care le cunoaşte Kirito, urmând să returneze preţul minim pe care îl poate plăti Kirito pentru a câştiga.
Date de intrare
Fişierul de intrare sao.in conţine pe prima linie N, numărul de monştri, urmat de N linii cu căte două numere RM şi PM, reprezentând rezistenţa şi forţa de atac a monstrului. Pe următoarea linie de va afla M, numărul de oferte pe care le are Kirito, urmat de M linii cu câte 3 numere, R, P, C, reprezentând puterea de atac a sabiei, rezistenţa armurii şi preţul fiecărei oferte.
Date de ieşire
În fişierul de ieşire sao.out se va alfa un singur număr, reprezentând preţul minim pe care trebuie sa-l plătească Kirito.
Restricţii
- 1 ≤ N ≤ 10 000
- 1 ≤ M ≤ 1 000 000
- 1 ≤ R, P, C, RM, PM ≤ 2 000 000 000
- se garantează faptul că cel puţin o variantă de armură şi sabie pe care să le poată cumpăra Kirito astfel încât să învingă toţi monştrii.
Exemplu
sao.in | sao.out |
---|---|
1 10 10 2 9 9 2 11 11 7 | 7 |
Explicaţie
Kirito va alege a doua ofertă, deoarece este singura care-i garantează Victoria.