#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()


const int N1 = 40000003;
const int N2 = 41289407;

ll key[N2];
int val[N2];

int pos(ll u) {
    int i = u % N1;

    while (key[i] != 0 && key[i] != u) ++i;
    return i;
}



const int MAXN = 36;
long long A[MAXN];
long long B[MAXN];
long long G[MAXN];
long long order[MAXN];
long long n;



long long get(long long mask, long long reachable) {
    
    int id = pos(mask);
    if (key[id] == mask)
        return val[id];
    key[id] = mask;


    if (reachable == ((1ll << n) - 1ll)) {
        long long cur_b = 0;
        long long mn = 0;
        for (int j = 0; j < n; ++j) {
            long long i = order[j];
            if (!(mask & (1ll << i))) {
                mn = min(mn, cur_b - A[i]);
                cur_b += B[i] - A[i];
            }
        }
        val[id] = mn;
        return mn;
    }
    long long res = -1e18;
    long long mn_pos = -1;
    for (long long i = 0; i < n; ++i) {
        if ((reachable & (1ll << i)) && !(mask & (1ll << i))) {
            if (A[i] >= B[i]) {
                long long new_reach = reachable | G[i];
                //if (new_reach != reachable) {
                    long long tmp = min(-A[i], get(mask | (1ll << i), new_reach) - A[i] + B[i]);
                    res = max(res, tmp);
                //}
            } else {
                if (mn_pos == -1 || A[i] < A[mn_pos])
                    mn_pos = i;
            }
        }
    }
    if (mn_pos != -1) {
        long long i = mn_pos;
        long long new_reach = reachable | G[i];
        long long tmp = min(-A[i], get(mask | (1ll << i), new_reach) - A[i] + B[i]);
        res = max(res, tmp);
    }
    val[id] = res;
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m;
    cin >> n >> m;
    A[0] = 0;
    B[0] = 0;
    for (int i = 1; i < n; ++i) {
        cin >> A[i] >> B[i];
    }
    for (long long i = 0; i < n; ++i)
        G[i] = 1ll << i;
    for (int i = 0; i < m; ++i) {
        long long a, b;
        cin >> a >> b;
        G[a - 1] |= 1ll << (b - 1);
    }
    iota(order, order + n, 0);
    sort(order, order + n, [](int a, int b) {
        if (A[a] < B[a]) {
            if (A[b] < B[b])
                return A[a] < A[b];
            return true;
        }
        if (A[b] < B[b])
            return false;
        return A[a] > A[b];
    });
    long long kek = get(1ll, G[0]);
    cout << -kek << '\n';
    return 0;
}