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

using ll = long long;
using ld = long double;

#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)

int n, m;
vector<ll> g;
vector<ll> a, b;

unordered_map<ll, ll> mem;

ll dfs(ll mask) {
    if (mask == (1ll << n) - 1) {
        return 0;
    }
    auto it = mem.find(mask);
    if (it != mem.end()) {
        return it->second;
    }
    ll adj = 0;
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) {
            adj |= g[i];
        }
    }
    pair<ll, int> best_pos = { 1e18, -1 };
    pair<ll, int> best_neg = { -1e18, -1 };
    for (int i = 0; i < n; i++) {
        if ((adj >> i & 1) && !(mask >> i & 1)) {
            if ((g[i] & mask) != g[i]) continue;
            if (a[i] <= b[i]) {
                best_pos = min(best_pos, make_pair(a[i], i));
            } else {
                best_neg = max(best_neg, make_pair(b[i], i));
            }
        }
    }
    ll res = 1e18;
    for (int i = 0; i < n; i++) {
        if ((adj >> i & 1) && !(mask >> i & 1)) {
            if ((g[i] & mask) == g[i]) {
                if (i != best_pos.second && i != best_neg.second) {
                    continue;
                }
            }
            res = min(res, max(a[i], dfs(mask | (1ll << i)) + a[i] - b[i]));
        }
    }
    return mem[mask] = res;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    a.resize(n);
    b.resize(n);
    for (int i = 1; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    g.resize(n);
    while (m--) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        g[v] |= 1ll << u;
        g[u] |= 1ll << v;
    }
    cout << dfs(1) << '\n';
}