//#pragma GCC optimize ("O2")
//#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

//おそそう

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	if ((tmp & ma0) ^ ma0) {
		int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
		tmp = tmp << dig & ma1;
		tmp = tmp * 10 + (tmp >> 8) & ma2;
		tmp = tmp * 100 + (tmp >> 16) & ma3;
		tmp = tmp * 10000 + (tmp >> 32) & ma4;
		ci += (72 - dig >> 3);
	}
	else {
		tmp = tmp & ma1;
		tmp = tmp * 10 + (tmp >> 8) & ma2;
		tmp = tmp * 100 + (tmp >> 16) & ma3;
		tmp = tmp * 10000 + (tmp >> 32) & ma4;
		ci += 8;
		if (*ci++ == '0') {
			tmp = tmp * 10;
			ci++;
		}
	}
	return tmp;
}
void pakuri_sort(int N, ll A[]) {
	const int b = 8;
	ll tmp[100001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}
ll li[300];
int li2[300];

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint(), M = getint();
	int w[8];
	rep(i, N) w[i] = getint();

	ll lv[100001];
	rep(i, M) {
		ll l = getint();
		int v = getint();
		lv[i] = l << 32 | v;
	}
	pakuri_sort(M, lv);
	lv[M] = 1000000001ll;

	rep(i, 1 << N) {
		rep(j, N) if (i >> j & 1) li[i] += w[j];
		li[i] = li[i] << 30 | i;
	}
	sort(li, li + (1 << N));
	int saidai = 0;
	int k = 0;
	rep(i, 1 << N) {
		while ((lv[k] & (1 << 30) - 1) < li[i] >> 30) {
			if (saidai < lv[k] >> 32) saidai = lv[k] >> 32;
			k++;
		}
		li[i] = ll(saidai) << 30 | (li[i] & (1 << 30) - 1);
	}
	rep(i, 1 << N) li2[li[i] & (1 << 30) - 1] = li[i] >> 30;

	rep(i, N) {
		if (w[i] > (lv[0] & (1 << 30) - 1)) {
			printf("-1");
			return 0;
		}
	}
	int P[8];
	rep(i, N) P[i] = i;

	int kotae = 1e9;
	do {
		int tmp[8] = {};
		rep(p, N - 1) {
			int omosa = 1 << P[p];
			for (int q = p + 1; q < N; q++) {
				omosa |= 1 << P[q];
				int kari = tmp[p] + li2[omosa];
				if (tmp[q] < kari) tmp[q] = kari;
			}
		}
		if (kotae > tmp[N - 1]) kotae = tmp[N - 1];
		
	} while (next_permutation(P, P + N));

	printf("%d\n", kotae);

	Would you please return 0;
}
#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#define ri register signed
#define rd(x) x=read()
using namespace std;
const int N=2e5+5;
const int maxn=5e6+5;
const int mod=998244353;
inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline int ksm(int x,int y,int z){int ret=1;while (y){if (y&1) ret=(ret*x)%z;x=(x*x)%z;y>>=1;}return ret;}
int inv[maxn],fac[maxn],ifc[maxn]; 
void Init(int n)
{
    inv[1]=1;for (ri i=2;i<=n;i++)inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    fac[0]=1;for (ri i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    ifc[0]=1;for (ri i=1;i<=n;i++) ifc[i]=ifc[i-1]*inv[i]%mod;
}
int C(int n,int m){if (m>n || m<0) return 0;return fac[n]*ifc[m]%mod*ifc[n-m]%mod;}

int n,k,ans,res;
vector<int> T[N];
int dep[N];
void dfs(int u,int fa,int lim)
{
	for (int v:T[u]) if (v!=fa) dfs(v,u,lim);
	if (u!=1)
	{
		if (T[u].size()==1) dep[u]=0; 
		else
		{
			dep[u]=-n;
			int mn=n,mx=-n;
			for (int v:T[u]) if (v!=fa) mx=max(mx,dep[v]+1),mn=min(mn,dep[v]+1);
			if (mx+mn<0) dep[u]=mn;
			else dep[u]=mx;
			if (dep[u]==lim) {res++;dep[u]=-lim-1;}
		}
	}
	else 
	{
		int mn=n,mx=-n;
		for (int v:T[u]) mx=max(mx,dep[v]+1),mn=min(mn,dep[v]+1);
		if (mx+mn<0) dep[u]=mn;
		else dep[u]=mx;
		if (dep[u]>=0) res++;
	}
}
bool chk(int x)
{
	res=0;
	for (int i=1;i<=n;i++) dep[i]=0;
	dfs(1,0,x);
	return res<=k;
}
signed main()
{
	rd(n);rd(k);
	if (k==n) {puts("0");return 0;}
	for (int i=1,x,y;i<n;i++) rd(x),rd(y),T[x].push_back(y),T[y].push_back(x);
	int l=1,r=n;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if (chk(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<endl;
}