#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];
        }
    }
    ll res = 1e18;
    for (int i = 0; i < n; i++) {
        if ((adj >> i & 1) && !(mask >> i & 1)) {
            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';
}