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

Poți vedea testele pentru această problemă accesând atașamentele.

Vezi soluțiile 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.