#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,M=72;
	const ll INF=1e18;
	struct edges{
		int u,v;
	}e[M];
	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];
	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])if(v^fa){
			dfs(v,u);
			merge(root[u],root[v]);
		}
		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;
		}
		dfs(1);
		zj ans={0,0};
		for(;root[1];pop(root[1]))ans=ans+t[root[1]].x;
		return ans.a;
	}
	int fa[N],siz[N];
	int find(int x){
		return fa[x]==x?x:find(fa[x]);
	}
	ll ans;
	bool Dfs(int i,int cnt=n){
		if(cnt==1)return ans=min(ans,calc()),1;
		if(i>m)return 0;
		int u=e[i].u,v=e[i].v;
		int x=find(u),y=find(v);
		if(x^y){
			to[u].push_back(v),to[v].push_back(u);
			if(siz[x]>siz[y])swap(x,y);
			siz[y]+=siz[x],fa[x]=y;
			bool flag=Dfs(i+1,cnt-1);
			siz[y]-=siz[x],fa[x]=x;
			to[u].pop_back(),to[v].pop_back();
			if(flag)flag|=Dfs(i+1,cnt);
			return flag;
		}
		return Dfs(i+1,cnt);
	}
	void solve(){
		for(int i=2;i<=n;i++){
			cin>>a[i].a>>a[i].b;
		}
		for(int i=1;i<=m;i++){
			cin>>e[i].u>>e[i].v;
		}
		ans=INF;
		iota(fa,fa+1+n,0),fill(siz+1,siz+1+n,1);
		Dfs(1);
		cout<<ans<<endl;
	}
}
int main(){
	cin>>n>>m;
	if(n<=26)Solve1::solve();
	else Solve2::solve();
	return 0;
}