// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) ((x)&(-(x)))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
void fre(){
//	freopen("clear.in","r",stdin),freopen("clear.out","w",stdout);
}
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
int n,zsy;
const int NR=105;
ll c[NR],d[NR];
namespace sub{
	ll f[1<<24];
	int to[NR];
	void _solve(){
		F(i,1,n-1)cin>>c[i]>>d[i];
		F(_,1,zsy){
			int u,v; cin>>u>>v,--u,--v,to[v]|=(1<<u);
		} const int mx=(1<<(n-1))-1;
        F(s,1,mx)f[s]=infll;
		F(s,0,mx-1){
			const int t=s<<1|1;
			ll cur=0;
			F(i,1,n-1)if((s>>(i-1))&1)cur+=d[i]-c[i];
			F(i,1,n-1)if(!((s>>(i-1))&1)&&(to[i]&t))chkmin(f[s^(1<<(i-1))],max(f[s],c[i]-cur));
		} cout<<f[mx];
	}
}
int fa[NR];
ll ans=infll;
vector<int>vec[NR];
int cnt=0,dsu[NR],vis[NR];
inline int find(int x){ return dsu[x]==x?x:dsu[x]=find(dsu[x]); }
struct node{
	int u; ll a,b;
	bool operator<(const node&rhs)const{
		if((b<0)^(rhs.b<0))return(b<0)>(rhs.b<0);
		if(b<0)return a+b<rhs.a+rhs.b;
		return a>rhs.a;
	}
};
ll a[NR],b[NR];
ll Solve_(){
	F(i,1,n)dsu[i]=i,vis[i]=(i==1);
	priority_queue<node>q;
	F(i,2,n)a[i]=c[i],b[i]=d[i],q.push((node){i,a[i],b[i]});
	while(!q.empty()){
		const int u=q.top().u; q.pop(); 
		if(vis[u])continue; vis[u]=1;
		const int f=find(fa[u]);
		chkmax(a[f],a[u]-b[f]),b[f]+=b[u],dsu[u]=f;
		if(f>1)q.push({f,a[f],b[f]});
	}
	return a[1];
}
void findsol(int u){
	if(u==n+1)return chkmin(ans,Solve_()),void();
	F(i,0,SZ(vec[u])-1)fa[u]=vec[u][i],findsol(u+1);
}
void solve(){
	cin>>n>>zsy;
	if(n<=25)return sub::_solve();
	F(i,2,n)cin>>c[i]>>d[i],d[i]-=c[i];
	F(i,1,zsy){
		int u,v; cin>>u>>v,vec[v].push_back(u);
	} findsol(2),cout<<ans;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	fre(); int zsy=1;
	F(____,1,zsy)solve();
}