#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++)


// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#include <bits/extc++.h>

struct hash_for_hash_map {
    size_t operator()(size_t x) const {
        static const size_t D = std::chrono::steady_clock::now().time_since_epoch().count();
        return x * x + D;
    }
};

template<typename key_t, typename value_t, typename hash_t = hash_for_hash_map>
using hash_map = __gnu_pbds::gp_hash_table<key_t, value_t, hash_t>;

template<typename value_t, typename hash_t = hash_for_hash_map>
using hash_set = __gnu_pbds::gp_hash_table<value_t, __gnu_pbds::null_type, hash_t>;

template<typename key_t, typename value_t, typename comp = std::less<key_t>>
using ordered_map = __gnu_pbds::tree<key_t, value_t,
    comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<typename value_t, typename comp = std::less<value_t>>
using ordered_set = ordered_map<value_t, __gnu_pbds::null_type, comp>;

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

hash_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));
            }
        }
    }
    if (best_pos.second != -1) {
        best_neg.second = -1;
    }
    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);
    // mem.reserve(1e6);
    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';
}