#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;

const ll INF = 100000000000000;

int main()
{
    int n, m;
    cin >> n >> m;
    ll w[10];
    for(int i = 0; i < n; i++) cin >> w[i];
    ll l[100005], v[100005];
    for(int i = 0; i < m; i++) cin >> l[i] >> v[i];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(w[i] > v[j]){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    ll d[500]{0};
    for(int i = 0; i < (1 << n); i++){
        ll s = 0;
        for(int j = 0; j < n; j++){
            if((i >> j) & 1) s += w[j];
        }
        for(int j = 0; j < m; j++){
            if(s > v[j]) d[i] = max(d[i], l[j]);
        }
    }
    int p[10];
    ll ans = INF;
    for(int i = 0; i < n; i++) p[i] = i;
    do{
        ll e[10]{0};
        for(int i = 0; i < n; i++){
            int u = p[i];
            int b = (1 << u);
            for(int j = i - 1; j >= 0; j--){
                int v = p[j];
                b += (1 << v);
                e[u] = max(e[u], e[v] + d[b]);
            }
        }
        ans = min(ans, e[p[n - 1]]);
    }while(next_permutation(p, p + n));
    cout << ans << endl;
}

#include <bits/stdc++.h>
#include <unistd.h>

#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define pie 3.141592653589793238
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define UQ(x) (x).resize(distance((x).begin(),unique(x.begin(),x.end())))

using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::high_resolution_clock::now().time_since_epoch().count());

ll power(ll a,ll m,ll mod){
	ll ans = 1;
	while(m){
		if(m%2) ans *= a, ans %= (mod);
		a = (a*a) % mod;
		m >>= 1;
	}
	return ans;
}

struct custom_hash {  // Credits: https://codeforces.com/blog/entry/62393
 	static uint64_t splitmix64(uint64_t x) {
    	// http://xorshift.di.unimi.it/splitmix64.c
    	x += 0x9e3779b97f4a7c15;
    	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    	x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    	return x ^ (x >> 31);
  	}
 
  	size_t operator()(uint64_t x) const {
    	static const uint64_t FIXED_RANDOM =
        	chrono::steady_clock::now().time_since_epoch().count();
    	return splitmix64(x + FIXED_RANDOM);
  	}
  	size_t operator()(pair<int64_t, int64_t> Y) const {
    	static const uint64_t FIXED_RANDOM =
        	chrono::steady_clock::now().time_since_epoch().count();
    	return splitmix64(Y.first * 31 + Y.second + FIXED_RANDOM);
  	}
};

const long long inf = 1e18;
const long long M = 1000000007;



void solve(){
	ll i,j,_;
	ll n, m;
	ll mx = LLONG_MAX;
	cin >> n >> m;
	ll w[n];
	rep(i,0,n) cin >> w[i];
	sort(w,w+n);
	if(n > 1) swap(w[0], w[n - 2]);
	ll tmp[n];
	i = 0;
	ll l = 0, r = n - 1;
	// while(i < n) {
	// 	if(i%2) tmp[i] = w[r], r--;
	// 	else tmp[i] = w[l],l++;
	// 	i++;
	// }
	// rep(i,0,n) w[i] = tmp[i];
	ll l1[m],r1[m];
	_ = 10000;
	rep(i,0,m) cin >> l1[i] >> r1[i];
	do {
	ll dp[n][n];
	rep(i,0,n)rep(j,0,n) dp[i][j] = 0;
	
ll bl = 0,t;
	rep(t,0,m) {
		l = l1[t], r = r1[t];
		rep(i,0,n) {
			ll now = w[i];
			// cout << now << ' ' << r << endl;
			if(now > r) {
				cout << -1 << endl;
				return;
				// bl = 1;
			}
			rep(j,i + 1,n) {
				now += w[j];
				if(now > r) {
					dp[i][j] = max(dp[i][j], l);
					break;
				}
			}
		}
		if(bl) break;
	}
	if(bl) continue;
	// rep(i,0,n) {
	// 	rep(j,0,n) {
	// 		cout << dp[i][j] << ' ';
	// 	}
	// 	cout << endl;
	// }
	ll k;
	rep(i,1,n) {
		rep(j,0,n) {
			r = j + i;
			if(r >= n) break;
			rep(k,j,r+1) {
				dp[j][r] = max(dp[j][r], dp[j][k] + dp[k][r]);
			}
		}
	}
	mx = min(mx, dp[0][n-1]);
	// if(mx == 3802) cout << _ << endl;
// 	cout << dp[0][n-1] << endl;
//     if(dp[0][n-1] == 3802){
//         for(auto i : w) cout << i << ' ';
// 	cout << endl;
    // }
   
	}while ( std::next_permutation(w + 1,w + n - 1));
	// cout << _ << endl;
	if(mx == LLONG_MAX) mx = -1;
	cout << mx << endl;
}

int main()
{
	ios::sync_with_stdio(0);
 	cin.tie(0);
	ll T=1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}


