// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
const ll INF = 1e15;
ll n,m,maxw=0;
signed main(){
  init_io();
  cin >> n >> m;
  vector<ll> w(n),l(m+1),v(m+1),use(n);
  vector<P> lv(m);
  for(int i=0;i<n;i++){
    cin >> w[i];
    maxw = max(maxw,w[i]);
    use[i] = i;
  }
  for(int i=0;i<m;i++){
    cin >> lv[i].first >> lv[i].second;
  }
  sort(lv.begin(),lv.end());
  for(int i=m-1;i>=0;i--){
    l[i+1] = lv[i].first;
    v[i] = lv[i].second;
    if(i!=m-1){
      v[i] = min(v[i],v[i+1]);
    }
  }
  l[0] = 0;
  v[m] = INF;
  if(maxw > v[0]){
    cout << -1 << endl;
    return 0;
  }
  ll ans = INF;
  do{
    vector<ll> d(n,0);
    for(int i=1;i<n;i++){
      ll sum = w[use[i]];
      for(int j=i-1;j>=0;j--){
        sum += w[use[j]];
        auto itr = lower_bound(v.begin(),v.end(),sum);
        ll idx = distance(v.begin(),itr);
        d[i] = max(d[i],d[j]+l[idx]);
      }
    }
    ans = min(ans,d[n-1]);
  }while(next_permutation(use.begin(),use.end()));
  cout << ans << endl;
}

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
#include <queue>
#include <stack>
#include <ctype.h>

using namespace std;

typedef long long ll;

const int INF = (1<<30)-1;
const ll LINF = 1e18;

#define rep(i, n) for (int i = 0; i < n; i++)

template<class T> 
bool chmax(T &a, T b) {if (a < b) {a = b;return true;}else return false;}

template<class T> 
bool chmin(T &a, T b) {if (a > b) {a = b;return true;}else return false;}

vector<vector<ll> > memo;
map<ll,ll> mp;
set<pair<ll,ll> > st;

ll func(int i, int j, vector<ll> &s, set<pair<ll,ll> > &st) {
    if (memo[i][j] != -1)
        return memo[i][j];
    auto ite = st.lower_bound(make_pair(s[j+1]-s[i], 0));
    ite--;
    ll res = mp[ite->first];
    for (int k = i+1; k < j; k++)
        chmax(res, func(i, k, s, st)+func(k, j, s, st));
    return memo[i][j] = res;
}

int main() {
    int n, m;   cin >> n >> m;
    vector<ll> w(n), l(m), v(m);
    ll mx = 0;
    rep(i, n) {
        cin >> w[i];
        chmax(mx, w[i]);
    }
    
    rep(i, m) {
        cin >> l[i] >> v[i];
        st.insert(make_pair(v[i], l[i]));
        if (mp.count(v[i]))
            mp[v[i]] = max(mp[v[i]], l[i]);
        else 
            mp[v[i]] = l[i];
        if (v[i] < mx) {
            cout << -1 << endl;
            return 0;
        }
    }
    mp[0] = 0;
    auto pre = mp.begin();
    for (auto ite = mp.begin(); ite != mp.end(); ite++) {
        if (ite->first == 0)    continue;
        ite->second = max(ite->second, pre->second);
        pre++;
    }
    st.insert(make_pair(0,0));
    sort(w.begin(), w.end());
    ll ans = LINF;

    do {
        vector<ll> s(n+1, 0);
        memo.assign(n, vector<ll>(n, -1));
        rep(i, n)   s[i+1] = s[i] + w[i];
        chmin(ans, func(0, n-1, s, st));
    } while (next_permutation(w.begin(), w.end()));
    cout << ans << endl;
    return 0;
}

//小数点精度
//cout << fixed << std::setprecision(15) << y << endl;