Rezolvare PBinfo #2729

Te afli în universul SAO (Sword Art Online pentru necunoscători). Ai la dispoziție o sumă mică de bani și m oferte. Fiecare ofertă constă într-o armură de o anumită rezistență și o sabie de o anumită putere. Tu trebuie să învingi n monștri ale căror rezistențe și puteri sunt cunoscute. După ce ai învins un monstru, armura ta va pierde din rezistență o valoare egală cu valoarea puterii monstrului, iar sabia va pierde valoarea rezistenței monstrului. Tu vei avea nevoie de setul armură/sabie de o valoare minimă care poate să învingă toți cei n monștri.

Cerința

Știind n – numărul de monștri, rezistența și puterea fiecăruia și m – numărul de oferte, cu rezistența armurii, puterea sabiei și prețul, să se determine costul cel mai mic pentru a învinge toți cei n monștri.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale reprezentând rezistența respectiv puterea fiecărui monstru. Apoi se va citi numărul m și m triplete de numere naturale reprezentând rezistența, puterea și prețul echipamentelor.

Date de ieșire

Programul va afișa pe ecran numărul V, reprezentând costul cel mai mic pentru a învinge toți cei n monștrii.

Restricții și precizări

• 1 ≤ n,m ≤ 10.000
• cele 2*n+3*m numere citite vor fi mai mici sau egale cu 263.
• în cazul în care nu poate învinge toți monștrii, se va afișa -1.

Exemplu 1:

Intrare

1
10 10
2
9 9 2
11 11 7

Ieșire

7

Explicație

Doar cea de-a doua ofertă garantează victoria.

Exemplu 2:

Intrare

1
10 10
2
9 9 2
5 5 7

Ieșire

-1

Explicație

Niciuna dintre oferte nu garantează victoria.