#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=72,N1=20;
const long long PIN=4557430888798830399;
int n,m;
int len_list=0,e[N],ne[N],h[N];
long long a[N],b[N],f[1<<N1],g[1<<N1];
void add_once(int a,int b){
	e[len_list]=b;
	ne[len_list]=h[a];
	h[a]=len_list;
	len_list++;
}
long long solve1(){
	int i,j,k,x,y;
	long long s1;
	for(i=1;i<n;i++)
		scanf("%lld%lld",&a[i],&b[i]);
	for(i=1;i<(1<<n);i++)
		for(j=0;j<n;j++){
			if(i>>j&1) continue;
			g[i]+=b[j]-a[j];
		}
	memset(h,-1,sizeof h);
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add_once(--x,--y);
	}
	memset(f,PIN,sizeof f);
	f[0]=PIN,f[1]=0;
	for(i=1;i<(1<<n);i+=2)
		for(j=0;j<n;j++){
			if(!(i>>j&1)) continue;
			for(k=h[j];k>=0;k=ne[k]){
				if(i>>e[k]&1) continue;
				s1=max(f[i],a[e[k]]-g[i]);
				f[i|(1<<e[k])]=min(f[i|(1<<e[k])],s1);
			}
		}
	return f[(1<<n)-1];
}
long long solve2(){
	return 0;
}
int main(){
//	freopen("HP.in","r",stdin);
//	freopen("HP.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(n<=N1) printf("%lld",solve1());
	else printf("%lld",solve2());
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}