#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];
vector<int> g[40], h[40];

struct node
{
    ll lmx, sum;
    node operator + (const node &b)const { return (node){max(lmx, b.lmx - sum), sum + b.sum}; }
    bool operator < (const node &b)const { if ((sum >= 0) ^ (b.sum >= 0)) return sum >= 0; return sum >= 0 ? (lmx < b.lmx) : (lmx + sum > b.lmx + b.sum); }
}d[40], p[40], q[40];
vector<node> nw[40];
int tl;

void dfs2(int u)
{
    for (int v : h[u]) dfs2(v); tl = 0;
    for (int v : h[u])
    {
        int i = 0, j = 0, k = 0;
        while (i < tl && j < nw[v].size())
            if (p[i] < nw[v][j]) q[k++] = nw[v][j++];
            else q[k++] = p[i++];
        while (i < tl) q[k++] = p[i++];
        while (j < nw[v].size()) q[k++] = nw[v][j++];
        tl += nw[v].size();
        for (i = 0; i < tl; i++) p[i] = q[i];
    }
    nw[u].resize(tl); for (int i = 0; i < tl; i++) nw[u][i] = p[i];
    while (nw[u].size() && !(d[u] < nw[u].back())) d[u] = (d[u] + nw[u].back()), nw[u].pop_back();
    nw[u].emplace_back(d[u]);
}

void work()
{
    for (int i = 1; i <= n; i++) h[i].clear();
    for (int i = 2; i <= n; i++) h[fa[i]].emplace_back(i);
    for (int i = 1; i <= n; i++) d[i] = (node){a[i], b[i] - a[i]}, nw[i].clear();
    dfs2(1); node tmp = (node){0, 0};
    while (nw[1].size()) tmp = tmp + nw[1].back(), nw[1].pop_back();
    res = min(res, tmp.lmx);
}

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;
}