#include <bits/stdc++.h>

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
using ll = long long;
using namespace std;
const double PI = acos(-1);
const int M = 1000000007;
// const int M = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int mod(int n, int m = M) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

int exp(int n, int k, int m = M) {
  if (k == 0) return 1;
  if (k == 1) return n;
  int ax = exp(n, k / 2, m);
  ax = mod(ax * ax, m);
  if (k % 2) ax = mod(ax * n, m);
  return ax;
}

int gcd(int a, int b) {
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}

int solve(const vector<int> &v, const vector<ii> &b, const vector<int> &calc) {
  int n = v.size();
  int g[n][n];
  for (int i = 0; i < n; i++) {
    int sum = v[i];
    for (int j = i + 1; j < n; j++) {
      sum += v[j];
      int id = upper_bound(all(b), ii(sum - 1, INF)) - b.begin();
      id--;
      if (id == -1)
        g[i][j] = 0;
      else
        g[i][j] = calc[id];
    }
  }

  vector<int> d(n, 0);
  d[0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      d[j] = max(d[j], d[i] + g[i][j]);
    }
  }
  return d[n - 1];
}

//#define MULTIPLE_TEST_CASE
void solution() {
  int n, m;
  cin >> n >> m;
  vector<ii> b(m);
  vector<int> calc;
  vi v(n);
  int mx = -INF, mn = INF;
  for (int &x : v) cin >> x, mx = max(mx, x);
  for (ii &x : b) cin >> x.ss >> x.ff, mn = min(mn, x.ff);
  int ans = INF;

  if (mx > mn) {
    cout << -1 << endl;
    return;
  }

  vector<int> p(n, 0);
  for (int i = 0; i < n; i++) p[i] = i;
  sort(all(v));
  sort(all(b));

  for (ii x : b) {
    if (calc.size() == 0)
      calc.pb(x.ss);
    else
      calc.pb(max(calc.back(), x.ss));
  }

  do {
    vector<int> w;
    for (int x : p) w.pb(v[x]);
    ans = min(ans, solve(w, b, calc));
  } while (next_permutation(all(p)));
  cout << ans << endl;
}

int32_t main() {
  DESYNC;
  int t = 1;
#ifdef MULTIPLE_TEST_CASE
  cin >> t;
#endif
  while (t--) solution();
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
    int n,m;
  	int vdnsddglkdk; 
    cin>>n>>m;
    vector<pair<int,int>>a(m);
    for(int i=0;i<m;i++)
    {
        cin>>a[i].first>>a[i].second;
    }
    int k;
    cin>>k;
    vector<pair<int,int>>b(k);
    for(int j=0;j<k;j++)
    {
        cin>>b[j].first>>b[j].second;
    }
    ll l=0;
    ll tot=1<<k;
    for(ll mask=0;mask<tot;mask++)
    {
        vector<int>v(n+1);
        ll ans=0;
        for(int i=0;i<k;i++)
        {
            if(mask & (1<<i))
                v[b[i].second]=1;
            else
                v[b[i].first]=1;
        }
        for(int i=0;i<m;i++)
        {
            if(v[a[i].first] && v[a[i].second])
                ans++;
        }
        l=max(l,ans);
    }
    cout<<l<<endl;
    return 0;
}