#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
#define inf 1e9

int N, M, w[maxn];
int dis[10][10], ans = inf;
struct Data{
    int l, v;
    Data(){}
    Data(int l, int v){ this -> l = l, this -> v = v; }
}d[maxn];
struct segment_tree{
    static const int maxn = 100005;
    int rt, np, lc[maxn << 1], rc[maxn << 1], mx[maxn << 1];

    int newnode(){
        np++; lc[np] = rc[np] = mx[np] = 0;
        return np;
    }
    void pushup(int now){
        mx[now] = max(mx[lc[now]], mx[rc[now]]);
    }
    void build(int &now, int L, int R, Data *a){
        now = newnode();
        if(L == R){ mx[now] = a[L].l; return; }
        int m = L + R >> 1;
        build(lc[now], L, m, a);
        build(rc[now], m + 1, R, a);
        pushup(now);
    }
    int query(int now, int L, int R, int A, int B){
        if(A <= L && R <= B) return mx[now];
        int m = L + R >> 1, re = 0;
        if(A <= m) re = max(re, query(lc[now], L, m, A, B));
        if(B > m) re = max(re, query(rc[now], m + 1, R, A, B));
        return re;
    }
}st;

bool cmp(Data a, Data b){ return a.v < b.v; }
bool Fail(){
    int mn = inf, mx = 0;
    for(int i = 1; i <= N; i++) mx = max(mx, w[i]);
    for(int i = 1; i <= M; i++) mn = min(mn, d[i].v);
    return mx > mn;
}
void floyd(){
    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                dis[i][j] = max(dis[i][j], dis[i][k] + dis[k][j]);
}
bool vis[10]; int seq[10], sum[10];
void run(int i){
    if(i > N){
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++) dis[i][j] = -inf;
        for(int i = 1; i < N; i++) dis[i][i + 1] = 0;

        sum[0] = 0;
        for(int i = 1; i <= N; i++) sum[i] = sum[i - 1] + w[seq[i]];

        Data tmp;
        for(int lef = 1; lef < N; lef++)
            for(int rig = lef + 1; rig <= N; rig++){
                tmp.v = sum[rig] - sum[lef - 1];
                int r = lower_bound(d + 1, d + M + 1, tmp, cmp) - d - 1;
                tmp.v = max(sum[rig - 1] - sum[lef - 1], sum[rig] - sum[lef]);
                int l = lower_bound(d + 1, d + M + 1, tmp, cmp) - d;
                if(l <= r) dis[lef][rig] = max(dis[lef][rig], st.query(st.rt, 1, M, l, r));
            }
        
        floyd();
        ans = min(ans, dis[1][N]);

        return;
    }
    for(int j = 1; j <= N; j++){
        if(vis[j]) continue;
        vis[j] = 1, seq[i] = j;
        run(i + 1);
        vis[j] = 0;
    }
}
int main()
{

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++) scanf("%d", &w[i]);
    for(int i = 1; i <= M; i++) scanf("%d%d", &d[i].l, &d[i].v);

    if(Fail()){
        printf("-1\n");
    }
    else{
        sort(d + 1, d + M + 1, cmp);
        st.build(st.rt, 1, M, d);
        run(1);
        printf("%d\n", ans);
    }

    return 0;
}
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <array>
#include <numeric>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
typedef tuple<ll, ll, ll> tl3;

//typedef modint998244353 mint;

const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const double EPS = 1e-7;
const int MAX = 1e5 + 5;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> w(n);
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}

	sort(w.begin(), w.end());
	vector<int> l(m);
	vector<int> v(m);

	for (int i = 0; i < m; i++) {
		cin >> l[i] >> v[i];
	}

	vector<pii> b(m);
	for (int i = 0; i < m; i++) {
		b[i].first = v[i];
		b[i].second = l[i];
	}

	sort(b.begin(), b.end());



	sort(v.begin(), v.end());
	if (w[n - 1] > v[0]) {
		cout << -1 << endl;
		return 0;
	}

	vector<int> lim(m + 1);
	for (int i = 0; i < m; i++) {
		lim[i + 1] = max(lim[i], b[i].second);
	}

	vector<int> p(n);
	iota(p.begin(), p.end(), 0);
	ll ans = INF;
	do {

		vector<vector<ll>> g(n, vector<ll>(n));
		for (int i = 0; i < n; i++) {
			ll sum = w[p[i]];
			for (int j = i + 1; j < n; j++) {
				sum += w[p[j]];
				auto it = lower_bound(v.begin(), v.end(), sum);

				int k = (it - v.begin());
				//cout << k << endl;
				g[i][j] = lim[k];
				//cout << lim[k] << endl;
			}
		}
		/*
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << g[i][j] << " ";
			}
			cout << endl;
		}
		*/

		vector<ll> d(n);

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				d[j] = max(d[j], d[i] + g[i][j]);
			}
		}


		ans = min(ans, d[n - 1]);

	} while (std::next_permutation(p.begin(), p.end()));
	cout << ans << endl;
}


