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ștrii 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.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n , m;
    long long int sx=0 , sy=0;
    cin >> n;
    long long int x , y;
    for(int i = 1 ; i <= n ; ++i)
        cin >> x >> y , sx+=x , sy+=y;
    cin >> m;
    long long int min = 1000000000000001;
    bool ok = false;
    for(int i = 1 ; i <= m ; ++i)
    {
        long long int cost;
        cin >> x >> y >> cost;
        if(x >= sx && y >= sx)
            if(cost < min)
                min = cost , ok = true;
    }
    if(ok)
        cout << min;
    else
        cout << -1;
    return 0;
}