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

typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, f[30];
ll a[40], b[40], dp[33554432];

void Solve1()
{
    for (int i = 1; i <= m; i++)
    {
        int u, v; cin >> u >> v;
        if (u > 1) f[v] |= (1 << (u - 2));
    }

    int N = 1 << (n - 1);
    for (int st = 0; st < N; st++) dp[st] = inf; dp[0] = 0; 
    for (int st = 0; st < N; st++)
    {
        bool Fl = true;
        for (int i = 0; i < n - 1; i++)
            if (!((st >> i) & 1) && f[i + 2] && (st & f[i + 2]) == f[i + 2]) { Fl = false; break; }
        if (!Fl) continue;
        for (int i = 0; i < n - 1; i++)
            if (!((st >> i) & 1)) dp[st | (1 << i)] = min(dp[st | (1 << i)], max(0ll, dp[st] - b[i + 2]) + a[i + 2]);
    }
    cout << dp[N - 1];
}

ll res = inf;
int fa[40], id[40], rk[40];
vector<int> g[40], h[40];

void work()
{
    for (int i = 1; i <= n; i++) h[i].clear(), id[i] = i;
    for (int i = 2; i <= n; i++) h[fa[i]].emplace_back(i);
    sort(id + 1, id + n + 1, [&](int x, int y) { if ((a[x] <= b[x]) ^ (a[y] <= b[y])) return a[x] <= b[x]; return (a[x] <= b[x]) ? (a[x] < a[y]) : (b[x] > b[y]); });
    for (int i = 1; i <= n; i++) rk[id[i]] = i;

    priority_queue<pii> pq; pq.push(make_pair(-rk[1], 1));
    ll sum = 0, mxd = 0;
    while (pq.size())
    {
        int u = pq.top().second; pq.pop();
        for (int v : h[u]) pq.push(make_pair(-rk[v], v));
        mxd = max(mxd, sum + a[u]); sum += a[u] + b[u];
    }
    res = min(res, mxd);
}

void dfs(int ind)
{
    if (ind == n + 1)
    {
        work();
        return;
    }
    for (int u : g[ind]) fa[ind] = u, dfs(ind + 1);
}

void Solve2()
{
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[v].emplace_back(u);
    }
    dfs(2); cout << res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 2; i <= n; i++) cin >> a[i] >> b[i];
    if (n <= 26) Solve1();
    else Solve2();
	return 0;
}