//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = 42, inf = 1000111222;


vector <int> edge[max_n];

mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
    return uniform_real_distribution<ld>(l, r)(rng);
}

int n;

set <ll> have;

ll a[max_n], b[max_n] = {};

inline void gen (ll mask) {
    if (have.count(mask)) {
        return;
    }
    LOG(mask);
    ll full = mask;
    for (int i = 0; i < n; i++) {
        if (mask & (1ll << i)) {
            for (int to : edge[i]) {
                full |= 1ll << to;
            }
        }
    }
    have.insert(mask);
    if (full == ((1ll << n) - 1)) {
        return;
    }
    for (int i = 0; i < n; i++) {
        if (mask & (1ll << i)) {
            for (int to : edge[i]) {
                if (!(mask & (1ll << to))) {
                    bool ok = false;
                    for (int go : edge[to]) {
                        if (!(full & (1ll << go))) {
                            ok = true;
                            break;
                        }
                    }
                    if (ok) {
                        gen(mask | (1ll << to));
                    }
                }
            }
        }
    }
}

const ll linf = inf * 1ll * inf;


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> n >> m;
//    assert(n + m <= 72);
//    auto add_edge = [&] (int a, int b) {
//        edge[a].pb(b);
//        --m;
//    };
//    for (int i = 1; i < n; i++) {
//        int v = randll(0, i - 1);
//        add_edge(v, i);
//    }
//    while (m > 0) {
//        int u = randll(0, n - 1);
//        int v = randll(0, n - 1);
//        while (u == v) {
//            v = randll(0, n - 1);
//        }
//        if (u > v) {
//            swap(u, v);
//        }
//        add_edge(u, v);
//    }
//    gen(1);
//    LOG(len(have));
    for (int i = 1; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        --u, --v;
        edge[u].pb(v);
    }
    gen(1);
    vector <ll> cur(all(have));
    sort(all(cur), [&] (ll x, ll y) {
        return __builtin_popcountll(x) < __builtin_popcountll(y);
    });
    map <ll, int> from;
    int N = len(cur);
    for (int i = 0; i < N; i++) {
        from[cur[i]] = i;
    }
    vector <ll> dp(N);
    vector <ll> sc(N, -1);
    ll l = 0, r = 1e15 * 37;
    while (l < r) {
        ll mid = (l + r) / 2ll;
        for (int i = 0; i < N; i++) {
            dp[i] = -linf;
            sc[i] = -1;
        }
        dp[0] = 0;
        assert(cur[0] == 1);
        bool ok = false;
        for (int i = 0; i < N; i++) {
            if (dp[i] < 0) {
                continue;
            }
//            LOG(i);
            ll score = mid;
            ll mask = cur[i];
            ll full = mask;
            for (int j = 0; j < n; j++) {
                if (mask & (1ll << j)) {
                    score += b[j] - a[j];
                    for (int to : edge[j]) {
                        full |= 1ll << to;
                    }
                }
            }
            vector <int> nice[2];
            for (int j = 0; j < n; j++) {
                if (dp[i] & (1ll << j)) {
                    score += b[j] - a[j];
                    continue;
                }
                if (!(mask & (1ll << j))) {
                    if (full & (1ll << j)) {
                        nice[a[j] <= b[j]].pb(j);
                    }
                }
            }
            sort(all(nice[1]), [&] (int x, int y) {
                return a[x] < a[y];
            });
            bool done = true;
            ll gg = dp[i];
            for (auto &j : nice[1]) {
                if (score < a[j]) {
                    done = false;
                    break;
                }
                score += b[j] - a[j];
                gg |= 1ll << j;
            }
            if (full == ((1ll << n) - 1) && done) {
                sort(all(nice[0]), [&] (int x, int y) {
                    return min(-a[x], -a[x] + b[x] - a[y]) > min(-a[y], -a[y] + b[y] - a[x]);
                });
                ll S = score;
                for (auto &j : nice[1]) {
                    if (S < a[j]) {
                        done = false;
                        break;
                    }
                    S += b[j] - a[j];
                }
                if (done) {
                    ok = true;
                    break;
                }
            }
            for (int j = 0; j < n; j++) {
                if (mask & (1ll << j)) {
                    for (int to : edge[j]) {
                        if (!(mask & (1ll << to))) {
                            bool OK = false;
                            for (int go : edge[to]) {
                                if (!(full & (1ll << go))) {
                                    OK = true;
                                    break;
                                }
                            }
//                            LOG(OK);
                            if (OK) {
                                ll new_mask = mask | (1ll << to);
                                ll cur_score = score - a[to];
                                if (cur_score < 0) {
                                    continue;
                                }
                                cur_score += b[to];
                                if (sc[from[new_mask]] < cur_score) {
                                    sc[from[new_mask]] = cur_score;
                                    dp[from[new_mask]] = gg;
                                }
                            }
                        }
                    }
                }
            }
        }
        if (ok) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << r << '\n';
}