#include <bits/stdc++.h>
using namespace std;
#define N 45
#define M (1<<25)+5
#define ll long long
#define pb push_back
int n,m;
void W(ll &x,ll y) {x=min(x,y);}
namespace Sub1
{
	int rt[N];ll ans=1e18,a[N],b[N];vector<int> e[N];
	void dfs()
	{
		int u=0;vector<int> vc;
		for(int i=2;i<=n;++i) if(rt[i]==i)
		{
			if(!u) {u=i;continue;}
			if(a[i]<=b[i]) {if(a[u]>b[u] || a[i]<a[u]) u=i;}
			else if(a[u]>b[u] && b[i]>b[u]) u=i;
		}if(!u) {ans=min(ans,a[1]);return;}
		for(auto v:e[u])
		{
			v=rt[v];ll tA=a[v],tB=a[v];vc.clear();
			for(int i=2;i<=n;++i) if(rt[i]==u) rt[i]=v,vc.pb(i);
			if(a[u]<b[v]) b[v]-=a[u]-b[u];else a[v]+=a[u]-b[v],b[v]=b[u];
			dfs();a[v]=tA;b[v]=tB;for(auto i:vc) rt[i]=u;
		}
	}
	void slv()
	{
		for(int i=1;i<=n;++i) rt[i]=i;
		for(int i=2;i<=n;++i) scanf("%lld %lld",&a[i],&b[i]);
		for(int i=1,u,v;i<=n;++i) scanf("%d %d",&u,&v),e[v].pb(u);
		dfs();printf("%lld\n",ans);
	}
}
namespace Sub2
{
	int e[N];ll a[N],b[N],dp[M];
	void slv()
	{
		for(int i=1;i<n;++i) scanf("%lld %lld",&a[i],&b[i]);
		for(int i=1,u,v;i<=n;++i) scanf("%d %d",&u,&v),e[v-1]|=1<<u-1;
		fill(dp,dp+(1<<n-1)-1,1e18);
		for(int i=(1<<n-1)-1;i;--i)
			for(int j=1;j<n;++j) if(i>>j-1&1 && e[j]&i*2+1)
				W(dp[i^(1<<j-1)],max(dp[i]-b[j],a[j]));
		printf("%lld\n",dp[0]);
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	if(n>26) Sub1::slv();else Sub2::slv();return 0;
}