#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N=110,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int n,m,a[N],b[N];
struct edge{
	int v,nxt;
}e[N*2];
int head[N],cnt=2;
void add(int u,int v){
	e[cnt].v=v;
	e[cnt].nxt=head[u];
	head[u]=cnt++;
}
namespace rd{
	mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	int vis;
	unordered_map<int,int> ma;
	bool dfs(int idx,int w){
		if(idx==n)return 1;
		if(ma[vis]>=w)return 0;
		ma[vis]=w;
		vector<int> ve;
		for(int i=1;i<=n;i++){
			if((vis>>i)&1){
				for(int j=head[i];j;j=e[j].nxt){
					if(!((vis>>e[j].v)&1)&&w>=a[e[j].v]){
						ve.pb(e[j].v);
					}
				}
			}
		}
		shuffle(ve.begin(),ve.end(),rng);
		for(int x:ve){
			vis|=(1ll<<x);
			if(dfs(idx+1,w-a[x]+b[x]))return 1;
			vis&=(~(1ll<<x));
		}
		return 0;
	}
	bool check(int v){
		vis=2;
		return dfs(1,v);
	}
	void solve(){
		int l=0,r=1e18;
		while(l<r){
			ma.clear();
			int m=(l+r)>>1;
			if(check(m))r=m;
			else l=m+1;
		}
		cout<<l<<endl;
	}
}
signed main(){
//	freopen("clear.in","r",stdin);
//	freopen("clear.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=2;i<=n;i++)cin>>a[i]>>b[i];
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	rd::solve();
	return 0;
}