#include <cassert>
#include <iostream>
#include <algorithm>
#include <cstdio> 
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <cstdlib>
#include <memory.h>
#include <ctime>
#include <bitset>
#include <fstream>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <time.h>
#include <chrono>
#include <random>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#define UI unsigned int
#define LL long long
#define ll long long
#define GT(it,v) for(auto it:v)
#define FU(i,a,b) for(int i=(a);i<(b);i++)
#define FD(i,a,b) for(int i=(a);i>(b);i--)
#define LD long double
#define PI 3.1415926535897932384626
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define VLL vector<long long >
#define VVLL vector<vector<long long > >
#define VPLL vector<pair<long long, long long>>
#define VVPLL vector<vector<pair<long long, long long>>>
#define VD vector<double>
#define VVD vector<vector<double> >
#define VPD vector<pair<double,double> >
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
#define SORT(v) std::sort(v.begin(),v.end())
#define GSORT(v,T) sort(v.begin(),v.end(),greater<T>)
#define UNIQUE(v) decltype(v.begin()) it = unique(v.begin(),v.end()); v.resize(distance(v.begin(),it))
using namespace std;
LL inp, Inp; LL i1, i2, i3, i4, i5, i6, i7, i8;
LL MOD = 998244353, MOD1 = (LL)1e9 + 7, MOD2 = (LL)1e9 + 9; long long MOD3 = (long long)1e9 + 21 /*33*/;  double eps = 1e-9;
LL TMP = (chrono::high_resolution_clock::now().time_since_epoch().count() % MOD + MOD) % MOD;
auto STTMP = chrono::steady_clock::now();//auto ENTMP = chrono::steady_clock::now();
//ELTIME = double(chrono::duration_cast<chrono::milliseconds>(ENTMP - STTMP).count());
//time_t result = time(NULL); char SS[26]; ctime_s(SS, sizeof SS, &result);
//transform(SS, SS + 26, SS, [](char ch) {return ch == ' ' ? '_' : ch; }); printf("%s", SS);;
vector<vector<int>> G;
vector<int> vis, minD, maxN, neis;

int main() {
    ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.precision(20);
    srand((unsigned int)TMP);
    int N, K; cin >> N >> K;
    G.resize(N, vector<int>());
    for (int i = 0; i < N - 1; i++){
        cin >> i1 >> i2; i1--, i2--;
        G.at(i1).push_back(i2);
        G.at(i2).push_back(i1);
    }

    int low = 1, up = N;
    while (low < up) {
        int mid = (low + up) / 2;
        int use = 0;
        LL vcnt = 0;
        vis.assign(N, 0);
        minD.assign(N, 1e9);
        maxN.assign(N, -1e9);
        neis.assign(N, 0);
        for (int i = 0; i < N; i++) {
            neis.at(i) = G.at(i).size();
        }
        queue<int> leafs;
        for (int i = 0; i < N; i++) {
            if (neis.at(i) <= 1) {
                leafs.push(i);
                neis.at(i)++;
                maxN.at(i) = 0;
            }
        }
        while (!leafs.empty()) {
            int leaf = leafs.front(); leafs.pop();
            neis.at(leaf)--;
            if (!vis.at(leaf) && neis.at(leaf) <= 1) { // leaf
                vis.at(leaf) = 1; vcnt++;
                if (maxN.at(leaf) + minD.at(leaf) <= mid) {
                    maxN.at(leaf) = minD.at(leaf) - mid - 1;
                }
                else if(maxN.at(leaf) >= mid || vcnt == N){
                    minD.at(leaf) = 0, maxN.at(leaf) = -mid - 1; use++;
                }
                for (auto nei : G.at(leaf)) {
                    minD.at(nei) = min(minD.at(nei), minD.at(leaf) + 1);
                    maxN.at(nei) = max(maxN.at(nei), maxN.at(leaf) + 1);
                    leafs.push(nei);
                }
            }
        }
        if (use > K) {
            low = mid + 1;
        }
        else {
            up = mid;
        }
    }
    cout << low << "\n";


    return 0;
}

/**
*    author:  Dooloper
*    created: 11.10.2020 23:12:53
**/

#pragma region Macros
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)
#define repn(i,n) for(int i = 1; i <= (n); i++)
#define pb push_back
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const double PI = acos(-1);
const int mod = 1000000007;
class mint {
   long long x;
public:
   mint(long long x=0) : x((x%mod+mod)%mod) {}
   mint operator-() const {
     return mint(-x);
   }
   mint& operator+=(const mint& a) {
       if ((x += a.x) >= mod) x -= mod;
       return *this;
   }
   mint& operator-=(const mint& a) {
       if ((x += mod-a.x) >= mod) x -= mod;
       return *this;
   }
   mint& operator*=(const  mint& a) {
       (x *= a.x) %= mod;
       return *this;
   }
   mint operator+(const mint& a) const {
       mint res(*this);
       return res+=a;
   }
   mint operator-(const mint& a) const {
       mint res(*this);
       return res-=a;
   }
   mint operator*(const mint& a) const {
       mint res(*this);
       return res*=a;
   }
   mint pow(ll t) const {
       if (!t) return 1;
       mint a = pow(t>>1);
       a *= a;
       return a;
   }
   // for prime mod
   mint inv() const {
       return pow(mod-2);
   }
   mint& operator/=(const mint& a) {
       return (*this) *= a.inv();
   }
   mint operator/(const mint& a) const {
       mint res(*this);
       return res/=a;
   }

   friend ostream& operator<<(ostream& os, const mint& m){
       os << m.x;
       return os;
   }
};
#pragma endregion

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n,m;
  cin >> n >> m;
  vector<int> w(n);
  vector<int> sums(1 << n), mn(1 << n);
  rep(i,n) cin >> w[i];
  int mx = *max_element(w.begin(),w.end());
  for(int s = 0; s < (1 << n); ++s){
    int x = 0;
    for(int i = 0; i < n; ++i) if(s >> i & 1) x+= w[i];
    sums[s] = x;
  }
  for(int i = 0; i < m; ++i){
    int l,v;
    cin >> l >> v;
    if(v < mx){
      cout << -1 << "\n";
      return 0;
    }
    for(int s = 0; s < (1 << n); ++s) if(sums[s] > v) mn[s] = max(mn[s],l);
  }
  int ans = 1e9;
  vector<int> perm(n);
  iota(perm.begin(), perm.end(), 0);
  do{
    vector<int> pos(n);
    for(int i = 1; i < n; ++i){
      int s = 1 << perm[i];
      for(int j = i-1; j >= 0; --j){
        s |= 1 << perm[j];
        pos[i] = max(pos[i], pos[j] + mn[s]);
      }
    }
    ans = min(ans, pos[n-1]);
  }while(next_permutation(perm.begin(), perm.end()));
  cout << ans << "\n";
  return 0;
}