#include <bits/stdc++.h>
#define N 105
using namespace std;
typedef long long ll;

int n, m; ll ans;
struct dat {
	ll a, b;
	bool operator < (const dat _) const { 
		if ((b-a>=0)!=(_.b-_.a>=0)) return b-a>=0;
		if (b-a>=0) return a<_.a;
		else return b>_.b;
	}
	dat operator + (const dat _) const {
		dat r;
		r.a = max(a, a-b+_.a); 
		r.b = b-a+_.b-_.a+r.a;
		return r;
	}
} v[N], v2[N];

int e[N];
ll dp[(1<<26)+5], sum[N];
void solve1() {
	for (int i = 1, u, vv; i <= m; i++) {
		scanf("%d %d", &u, &vv);
		e[vv] |= 1<<(u-1); 
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[1] = 0;
	for (int s = 1; s < (1<<n); s++) {
		int c = __builtin_popcount(s), x = __lg(s&-s)+1;
		sum[c] = sum[c-1]-v[x].a+v[x].b;
		ll nw = dp[s]+sum[c];
		for (int i = 1; i <= n; i++) if ((~s>>(i-1)&1) && (e[i]&s)) {
			dp[s|(1<<(i-1))] = min(dp[s|(1<<(i-1))], max(dp[s],dp[s]+v[i].a-nw));
		}
	}
	ans = dp[(1<<n)-1];
}

vector<int> E[N]; 
int fa[N], vis[N], Fa[N];
int find(int x) { return x==Fa[x]?x:Fa[x]=find(Fa[x]); }
void DP() {
	set<pair<dat,int> > st;
	dat nw = (dat){0,0}; vis[1] = 1;
	iota(Fa+1,Fa+n+1,1);
	for (int i = 2; i <= n; i++) {
		vis[i] = 0; st.insert({v2[i]=v[i],i});
	}	
	while (!st.empty()) {
		int x = st.begin()->second; st.erase(st.begin());
		if (vis[find(fa[x])]) {
			vis[x] = 1;
			nw = nw+v2[x]; continue;
		}
		Fa[x] = find(fa[x]);
		st.erase({v2[fa[x]],fa[x]});
		v2[fa[x]] = v2[fa[x]]+v2[x];
		st.insert({v2[fa[x]],fa[x]});
	}
	ans = min(ans, nw.a);
}
void dfs(int x) {
	if (x > n) { DP(); return; }
	for (auto f : E[x]) {
		fa[x] = f; dfs(x+1);
	}
}
void solve2() {
	for (int i = 1, u, vv; i <= m; i++) {
		scanf("%d %d", &u, &vv);
		E[vv].push_back(u);
	}
	dfs(2);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 2; i <= n; i++) {
		scanf("%lld %lld", &v[i].a, &v[i].b);
	}
	ans = 1e18;
	if (n <= 26) solve1();
	else solve2();
	printf("%lld\n", ans);
	return 0;
}