#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e8;
int n,m,res=0,cnt=0,tot=0;
int b[300005];
ll pp[300005],qq[300005];
int h[300005],to[600005],ver[600005];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void add(int x,int y) {
	to[++cnt]=y;
	ver[cnt]=h[x];
	h[x]=cnt;
}
void work(int x,int fa,int mid) {
	pp[x]=-INF;qq[x]=INF;
	for(register int i=h[x];i;i=ver[i]) {
		int y=to[i];
		if(y==fa) continue;
		work(y,x,mid);
		pp[x]=max(pp[x],pp[y]+1);
		qq[x]=min(qq[x],qq[y]+1);
	}
	if(pp[x]+qq[x]<=mid) pp[x]=-INF;
	if(qq[x]>mid&&b[x]==1) pp[x]=max(pp[x],(long long)0);
	if(pp[x]==mid) pp[x]=-INF,qq[x]=0,++tot;
}
int check(int x) 
{
	tot=0;
	work(1,-1,x);
	if(pp[1]>=0) ++tot;
	return tot<=m;
}
int main() 
{
	n=read(),m=read();
	for(register int i=1;i<=n;++i) b[i]=1;
	for(register int i=1;i<n;++i) 
	{
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	int L=0,R=n;
	while(L<=R) {
		int mid=L+R>>1;
		if(check(mid)) R=mid-1,res=mid;
		else L=mid+1;
	}
	printf("%d\n",res);
	return 0;
}
#include<bits/stdc++.h>
#define Re register
using namespace std;

const int N=10,M=100005;

struct Node {
	int L,V;
	bool operator <(const Node& b) const {
		return L==b.L ? V<b.V : L<b.L;
	}
	bool operator <(const int& b) const {
		return V<b;
	}
}b[M];

int n,m;
int Max;
int c[N];
int p[N];
int f[N];
int Maxx[M];
int sum[N];
int ans=0x7f7f7f7f;

inline int rd()
{
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(Re int i=1;i<=n;i++)
	{
		c[i]=rd();
		p[i]=i;
		Max=max(Max,c[i]);
	}
	for(Re int i=1;i<=m;i++)
	{
		b[i].L=rd();
		b[i].V=rd();
		if(Max>b[i].V)
		{
			printf("-1");
			return 0;
		}
	}
	sort(b+1,b+m+1);
	for(Re int i=m-1;i>0;i--)
	{
		b[i].V=min(b[i].V,b[i+1].V);
	}
	do
	{
		memset(f,0,sizeof f);
		for(Re int i=1;i<=n;i++)
		{
			sum[i]=sum[i-1]+c[p[i]];
		}
		for(Re int i=2;i<=n;i++)
		{
			f[i]=f[i-1];
			for(Re int j=1;j<i;j++)
			{
				int x=lower_bound(b+1,b+m+1,sum[i]-sum[j-1])-b-1;
				f[i]=max(f[i],f[j]+b[x].L);
			}
		}
		ans=min(ans,f[n]);
	}while(next_permutation(p+1,p+n+1));
	printf("%d",ans);
	return 0;
}