    #include <bits/stdc++.h>
    using namespace std;
    #include <math.h>
    #include <iomanip>
    #include <cstdint>
    #include <string>
    #include <sstream>
    template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
    template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
    #define rep(i,n) for (int i = 0; i < (n); ++i)
    typedef long long ll;
    using P = pair<int,int>;
    const int INF=1001001001;
    const int mod =1e9+7;
    
    int main() {
      int N,M;
      cin>>N>>M;
      vector<int>w(N),l(M),v(M);
      rep(i,N){cin>>w[i];}
      rep(i,M){cin>>l[i]>>v[i];}
      int mx=*max_element(w.begin(),w.end());
      vector<pair<int,int>>p(M);
      rep(i,M){
        if(mx>v[i]){cout<<-1<<endl;return 0;}
        p[i]={v[i],l[i]};
      }
      sort(p.begin(),p.end());
      rep(i,M-1){
        chmax(p[i+1].second,p[i].second);
      }
      vector<int>x(N);
      iota(x.begin(),x.end(),0);
      ll ans=INF;
      do{
        vector<ll>dp(N);
        rep(i,N){
          ll now=0;
          for(int j=i;j<N;j++){
            now+=w[x[j]];
            int e=lower_bound(p.begin(),p.end(),P(now,0))-p.begin();
            if(e>0){chmax(dp[j],dp[i]+p[e-1].second);}
          }
        }
        chmin(ans,dp[N-1]);
      }while(next_permutation(x.begin(),x.end()));
      cout<<ans<<endl;
      return 0;
    }
#include <bits/stdc++.h>
#define readFast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define output(x) ((int)x && cout << "YES\n") || cout << "NO\n";
using namespace std;

#ifdef LOCAL
#define read() ifstream fin("date.in.txt");
#else
#define read() readFast;
#endif

const int N = 10;
const int M = 1e5 + 5;

int n, m;
ll v[N], wMax, l, w, wAct;
ll ans = LLONG_MAX, drum;
ll dist[N][N];

vector<pair<ll,ll>> restrictii;

void searchMaxDistance(int act, ll d) {
    if(act == n) {
        drum = max(drum, d);
        return;
    }
    for (int i = act + 1; i <= n; ++i) {
        searchMaxDistance(i, d + dist[act][i]);
    }
}

bool cmp(pair<ll,ll> a, pair<ll, ll> b) {
    if(a.first == b.first)
        return a.second > b.second;
    return a.first < b.first;
}

int main() {
    read();

    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
        wMax = max(wMax, v[i]);
    }
    for (int i = 1; i <= m; ++i) {
        fin >> l >> w;
        if(w < wMax) {
            cout << -1;
            return 0;
        }
        restrictii.push_back({w, l});
    }
    restrictii.push_back({0, 0});
    sort(restrictii.begin(), restrictii.end(), cmp);

    ll mx = 0;
    for (int i = 0; i < sz(restrictii); ++i) {
        mx = max(mx, restrictii[i].second);
        restrictii[i].second = mx;
    }

    vector<int> p(n + 1);
    iota(p.begin(), p.end(), 0);

    do {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j)
                dist[i][j] = 0;
        }
        //for (int i = 1; i <= n; ++i)
        //    cout << p[i] << " ";
        //cout << '\n';

        for (int i = 1; i < n; ++i) {
            wAct = v[p[i]];
            for (int j = i + 1; j <= n; ++j) {
                wAct += v[p[j]];

                int posNeed = upper_bound(restrictii.begin(), restrictii.end(), make_pair(wAct, 0ll)) - restrictii.begin();
                --posNeed;

                dist[i][j] = restrictii[posNeed].second;
            }
        }
        /*for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                cout << dist[i][j] << " " ;
            }
            cout << '\n';
        }
        cout << '\n';
        */drum = 0;
        searchMaxDistance(1, 0);
        ans = min(ans, drum);
        //break;
    } while(next_permutation(p.begin() + 1, p.end()));

    cout << ans << '\n';
    return 0;
}
