#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;

struct part {
    int v, l;
    part(int v=0, int l=0): v(v), l(l) {}
};

int main() {
    // 全探索、重さでソート、最長路、二分探索
    int N, M;
    cin >> N >> M;
    vector<int> W(N);
    rep(i, N) cin >> W[i];
    sort(W.begin(), W.end());
    vector<part> LV(M);
    int maxV = 0, minV = 1e9;
    rep(i, M) {
        int l, v;
        cin >> l >> v;
        maxV = max(maxV, v);
        minV = min(minV, v);         
        LV[i].v = v;
        LV[i].l = l;        
    }
    if (W[N-1] > minV) {
        cout << -1 << '\n';
        return 0;
    }
    sort(LV.begin(), LV.end(), [&] (const part& x, const part& y) { return x.v < y.v; });
    map<int, ll> mp;
    rep(i, M) {
        int key = LV[i].v;
        int value = LV[i].l;
        if (mp[key] < value) {
            mp[key] = value;
        }
    }
    int maxL = 0;
    for (auto &p : mp) {
        if (p.second > maxL) {
            maxL = p.second;
        }
        p.second = maxL;
    }
    mp[INF] = maxL;
    vector<int> pos(N);
    rep(i, N) pos[i] = i;
    ll ans = 1e16;
    do {
        vector<P> ws(N);
        rep(i, N) ws[i].first = W[pos[i]];
        vector<vector<ll>> dist(N, vector<ll> (N));
        rep(i, N) for (int j = i+1; j < N; j++) {
            // iからjまでの重さが十分の距離があるか
            int temp = 0, d = 0;
            for (int k = i; k <= j; k++) {
                temp += ws[k].first;
                if (k != j) d += ws[k].second;
            }
            if (temp <= minV) continue;
            auto it = mp.lower_bound(temp);
            if (it == mp.begin()) continue;
            it--;
            dist[i][j] = it -> second;
        }
        vector<ll> dp(N);
        rep(i, N) for (int j = i+1; j < N; j++) {
            dp[j] = max(dp[j], dp[i] + dist[i][j]);            
        }
        ans = min(ans, dp[N-1]);
    } while (next_permutation(pos.begin(), pos.end()));
    cout << ans << '\n';
    return 0;
}
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, c[10], dl[10], vis[10], ans = 0x3f3f3f3f, lx[10], db[10];
struct judge {
    int l;
    int v;
};
judge a[100010];
bool tmp(judge x, judge y)
{
    if (x.l != y.l) return x.l < y.l;
    else return x.v > y.v;
}
int findl(int x)
{
    int b, e, t;
    b = 1, e = m, t = b + e >> 1;
    while (b < e)
    {
        if (a[t].v >= x) e = t-1;
        else b = t ;
        t = b + e +1>> 1;
    }
    if (a[b].v >= x) return 0;
    return a[b].l;
}
void fact()
{
    memset(lx, 0, sizeof lx);
    for (int i = 1; i <= n; i++)
    {
        db[i] = db[i - 1] + c[dl[i]];
    }
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
        {
            int l = findl(db[i] - db[j - 1]);
            lx[i] = max(lx[i], lx[j] + l);
        }
    ans = min(ans, lx[n]);
}
void dfs(int i)
{
    if (i == n + 1)
    {
        fact();
        return;
    }
    for (int j = 1; j <= n; j++)
    {
        if (!vis[j])
        {
            vis[j] = 1;
            dl[i] = j;
            dfs(i + 1);
            vis[j] = 0;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)  cin >> c[i];
    for (int i = 1; i <= m; i++)  cin >> a[i].l >> a[i].v;
    sort(a + 1, a + m + 1, tmp);
    for (int i = m - 1; i > 0; i--) a[i].v = min(a[i].v, a[i + 1].v);
    for (int i = 1; i <= n; i++) if (c[i] > a[1].v) { cout << -1; return 0; }
    dfs(1);
    cout << ans;
}
