#include <bits/stdc++.h>

using namespace std;
int mas[8];
int dist[256];
int dist1[8][8];
int ans[8];
pair<int,int> parts[100000];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,ma=0;
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>mas[i];
        ma=max(ma,mas[i]);
    }
    for(int i=0; i<m; i++){
        cin>>parts[i].first>>parts[i].second;
        if(ma>parts[i].second){
            cout<<-1;
            return 0;
        }
    }
    for(int i=0; i<(1<<n); i++){
        if(__builtin_popcount(i)<2) continue;
        int sum=0;
        for(int j=0; j<n; j++){
            if(i&(1<<j)){
                sum+=mas[j];
            }
        }
        for(int k=0; k<m; k++){
            if(sum>parts[k].second){
                dist[i]=max(dist[i],parts[k].first);
            }
        }
    }
    int ANS1=1e9;
    vector<int> a;
    for(int i=0; i<n; i++) a.push_back(i);
    do{
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                dist1[i][j]=0;
        for(int i=1; i<(1<<n); i++){
            int mi=n+1,ma=0;
            for(int j=0; j<n; j++){
                if(i&(1<<j)){
                    mi=min(mi,a[j]);
                    ma=max(ma,a[j]);
                }
            }
            dist1[mi][ma]=max(dist1[mi][ma],dist[i]);
        }
        ans[0]=0;
        for(int i=1; i<=n-1; i++){
            int a=ans[i-1];
            for(int j=0; j<i; j++){
                a=max(a,dist1[j][i]+ans[j]);
            }
            ans[i]=a;
        }
        ANS1=min(ANS1,ans[n-1]);
    }while(next_permutation(a.begin(),a.end()));
    cout<<ANS1;
}

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FIO ios_base::sync_with_stdio(false); cin.tie(0);
#define trav(x,a) for (auto& x: a)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define mem(a,v) memset((a), (v), sizeof (a))
#define endl "\n"
#define case(t) cout << "Case #" << (t) << ": "
#define reada(a, n) for (int _i = 0; _i < (n); _i++) read(a[_i])
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;
const double eps = 1e-9;

template<class T> void read(T& x) { cin >> x; }
template<class X, class Y> void read(pair<X,Y>& a) { read(a.first), read(a.second); }
template<class T, size_t U> void read(array<T,U>& x) { for (int i = 0; i < U; i++) read(x[i]); }
template<class T> void read(vector<T>& x) { trav(y, x) read(y); }
template<class T, class... O> void read(T& x, O&... y) { read(x), read(y...); }

string to_string(const char& x) { return string(1,x); }
string to_string(const char*& x) { return (string)x; }
string to_string(const string& x) { return x; }
template<class T, class U> string to_string(const pair<T,U>& x) { return to_string(x.first) + " " + to_string(x.second); }
template<class T, size_t U> string to_string(const array<T,U>& x) { string ret = ""; for (int i = 0; i < U; i++) ret += (!i ? "" : " ") + to_string(x[i]); return ret; }
template<class T> string to_string(const vector<T>& x) { string ret = ""; bool f = 0; trav(y, x) ret += (!f ? "" : " ") + to_string(y), f = 1; return ret; }
template<class T> string to_string(const set<T>& x) { string ret = ""; bool f = 0; trav(y, x) ret += (!f ? "" : " ") + to_string(y), f = 1; return ret; }
void print() { cout << endl; }
template<class T> void pr(const T& x) { cout << to_string(x); }
template<class T, class... O> void print(const T& x, const O&... y) { pr(x); if (sizeof...(y)) pr(" "); print(y...); }

int pref_dist[N], pref_weight[N];

int main() {
  FIO
  int n, m; read(n, m);
  vector<int> w(n); read(w);
  vector<pair<int,int>> arr(m); read(arr);
  map<int,int> mx_dist;
  int mxw = *max_element(all(w));
  trav(x, arr) {
    if (x.second < mxw) {
      print("-1");
      return 0;
    }
    if (mx_dist.count(x.second))
      mx_dist[x.second] = max(mx_dist[x.second], x.first);
    else
      mx_dist[x.second] = x.first;
  }
  int len = 0;
  for (auto x: mx_dist) {
    pref_weight[len] = x.first;
    pref_dist[len] = x.second;
    if (len)
      pref_dist[len] = max(pref_dist[len], pref_dist[len-1]);
    len++;
  }
  vector<int> ind(n, 0);
  iota(all(ind), 0);
  int ans = inf;
  do {
    vector<int> pos(n, 0);
    for (int i = 0; i < n; i++) {
      int pref = w[ind[i]], nx = 0;
      if (i) pos[i] = pos[i-1];
      for (int j = i-1; j >= 0; j--) {
        pref += w[ind[j]];
        auto it = lower_bound(pref_weight, pref_weight + len, pref) - pref_weight - 1;
        if (it < 0)
          continue;
        pos[i] = max(pos[i], pos[j] + pref_dist[it]);
      }
    }
    // print(ind, "+", pos);
    ans = min(ans, pos[n-1]);
  } while (next_permutation(all(ind)));
  print(ans);
  return 0;
}
