#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
int n,m;
namespace Solve1{
	const int N=26,M=1<<N;
	const ll INF=1e18;
	ll f[M],sum[M],a[N],b[N];
	int U,to[N];
	void solve(){
		U=(1<<n)-1;
		for(int i=1;i<n;i++)cin>>a[i]>>b[i];
		for(int u,v;m--;){
			cin>>u>>v,u--,v--;
			to[u]|=1<<v,to[v]|=1<<u;
		}
		fill(f,f+1+U,INF);
		f[1]=0;
		for(int S=1;S<U;S++){
			int i=__builtin_ctz(S);
			sum[S]=sum[S^(1<<i)]-a[i]+b[i];
		}
		for(int S=1;S<U;S+=2){
			int i=__builtin_ctz(S);
			sum[S]=sum[S^(1<<i)]-a[i]+b[i];
			for(int v=0;v<n;v++)if(~S>>v&1){
				if(S&to[v]){
					int T=S|(1<<v);
					f[T]=min(f[T],max(f[S],a[v]-sum[S]));
				}
			}
		}
		cout<<f[U]<<endl;
	}
}
namespace Solve2{
	const int N=72;
	const ll INF=1e18;
	struct zj{
		ll a,b;
		zj operator + (const zj &x)const{
			if(x.a>b)return {a+x.a-b,x.b};
			return {a,b+x.b-x.a};
		}
		bool operator < (const zj &x)const{
			int t1=a<=b,t2=x.a<=x.b;
			if(t1^t2)return t1;
			if(t1)return a<x.a;
			return b>x.b;
		}
	}a[N],b[N];
	struct tree{
		zj x;
		int ls,rs,dis;
	}t[N];
	void merge(int &x,int y){
		if(!x||!y){
			x|=y;return;
		}
		if(t[y].x<t[x].x)swap(x,y);
		merge(t[x].rs,y);
		if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);
		t[x].dis=t[t[x].rs].dis+1;
	}
	void pop(int &x){
		int r1=t[x].ls,r2=t[x].rs;
		merge(x=r1,r2);
	}
	int root[N];
	vector<int>to[N];
	void dfs(int u,int fa=0){
		for(int v:to[u]){
			dfs(v,u);
			merge(root[u],root[v]);
		}
		if(u==1)return;
		for(;root[u]&&t[root[u]].x<a[u];pop(root[u])){
			a[u]=a[u]+t[root[u]].x;
		}
		t[u]={a[u],0,0,1},merge(root[u],u);
	}
	ll calc(){
		for(int i=1;i<=n;i++){
			root[i]=0,a[i]=b[i];
		}
		dfs(1);
		zj ans={0,0};
		for(;root[1];pop(root[1]))ans=ans+t[root[1]].x;
		return ans.a;
	}
	ll ans;
	vector<int>p[N];
	void Dfs(int i){
		if(i>n){
			// debug(i,ary(to,1,i));
			ans=min(ans,calc());return;
		}
		for(int t:p[i]){
			to[t].push_back(i);
			Dfs(i+1);
			to[t].pop_back();
		}
	}
	void solve(){
		for(int i=2;i<=n;i++){
			cin>>b[i].a>>b[i].b;
		}
		for(int i=1,u,v;i<=m;i++){
			cin>>u>>v,p[v].push_back(u);
		}
		ans=INF;
		Dfs(2);
		cout<<ans<<endl;
	}
}
int main(){
	cin>>n>>m;
	if(n<=26)Solve1::solve();
	else Solve2::solve();
	return 0;
}