    #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<ll,ll>;
    const int INF=1001001001;
    const int mod=998244353;

    int main() {
      int N,M;
      cin>>N>>M;
      vector<int>w(N);
      int wmx=0;
      rep(i,N){cin>>w[i];chmax(wmx,w[i]);}
      vector<int>l(M),v(M);
      int vmn=INF;
      vector<P>b(M);
      rep(i,M){cin>>l[i]>>v[i];b[i]={v[i],l[i]};chmin(vmn,v[i]);}
      if(wmx>vmn){cout<<-1<<endl;return 0;}
      sort(b.begin(),b.end());
      rep(i,M){
        if(i>0){chmax(b[i].second,b[i-1].second);}
      }
      vector<int>num(N);
      iota(num.begin(),num.end(),0);
      ll ans=1e18;
      do{
        vector<ll>dp(N);
        rep(i,N){
          ll mx=0;
          for(int j=i;j<N;j++){
            mx+=w[num[j]];
            int r=lower_bound(b.begin(),b.end(),P(mx,0))-b.begin();
            if(r-1>=0){chmax(dp[j],dp[i]+b[r-1].second);}
          }
        }
        chmin(ans,dp[N-1]);
      }while(next_permutation(num.begin(),num.end()));
      
      cout<<ans<<endl;
      return 0;
    }
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	vector<int>weight(N);
	for (auto &i : weight)cin >> i;
	vector<int>l(M);
	vector<int>d(M);
	for (int i = 0; i < M; i++) {
		cin >> l[i] >> d[i];
	}
	if (*max_element(weight.begin(), weight.end()) > *min_element(d.begin(), d.end())) {
		cout << -1 << endl;
		return 0;
	}
	vector<int>sum(1 << N);
	for (int i = 0; i < 1 << N; i++) {
		for (int j = 0; j < N; j++) {
			if ((i >> j) & 1) {
				sum[i] += weight[j];
		//		cout << i << " " << sum[i] << endl;
			}
		}
	}
	map<int, int>mp;
	for (int i = 0; i < M; i++) {
		mp[d[i]] = 0;
	}
	for (auto i : sum)mp[i] = 0;
	int cnt = 0;
	for (auto &i : mp) {
		i.second = cnt++;
	}
	vector<int>mn(cnt);
	for (int i = 0; i < M; i++) {
		mn[mp[d[i]]] = max(l[i], mn[mp[d[i]]]);
	}
	for (int i = 1; i < cnt; i++) {
		mn[i] = max(mn[i], mn[i - 1]);
	}
	int ans = MOD;
	vector<int>p(N);
	for (int i = 0; i < N; i++) {
		p[i] = i;
	}
	do {
		vector<int>place(N);
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < i; j++) {
				int bit = 0;
				for (int k = j; k <= i; k++) {
					bit |= 1 << p[k];
				}
			//	cout << i << " " << j << " " << bit << endl;
				place[i] = max(place[i], place[j] + mn[mp[sum[bit]] - 1]);
			}
		}
	//	cout << place.back() << endl;
		ans = min(ans, place.back());
	} while (next_permutation(p.begin(), p.end()));
	cout << ans << endl;
}