Fişierul intrare/ieşire:	sao.in, sao.out	Sursă	ad-hoc
Autor	Andreescu Mihai, Barbalau Antonio	Adăugată de	Andreescu Mihai •mihai995
Timp execuţie pe test	0.1 sec	Limită de memorie	500 kbytes
Scorul tău	N/A	Dificultate	1/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

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

Explicaţie

Kirito va alege a doua ofertă, deoarece este singura care-i garantează Victoria.