#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef pair<int,int> Pair;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

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

int N,M;
VL dp(8,-1);
ll L[8][8];

ll rec(int v){
    if(dp[v] != -1) return dp[v];
    ll ret = 0;
    FOR(to,v+1,N){
        chmax(ret, rec(to) + L[v][to]);
    }
    return dp[v] = ret;
}

void Main(){
    cin >> N >> M;
    ll MINV = LINF, MAXW = 0;
    VL w(N); REP(i,N) cin >> w[i], chmax(MAXW,w[i]);
    VL l(M),v(M); REP(i,M) cin >> l[i] >> v[i], chmin(MINV, v[i]);
    if(MINV<MAXW){
        cout << -1 << en;
        return;
    }

    VI p(M); REP(i,M) p[i] = i;
    auto cmp = [&](int i, int j){return v[i]<v[j];}; sort(ALL(p), cmp);
    VL mx(M+1,0); REP(i,M) chmax(mx[i+1], max(mx[i],l[p[i]]));

    ll ans = LINF;
    VI q(N); REP(i,N) q[i] = i;
    do{
        VL ww(N); REP(i,N) ww[i] = w[q[i]];
        VL sum(N+1,0); REP(i,N) sum[i+1] = sum[i] + ww[i];

        REP(i,N-1)FOR(j,i+1,N){
            ll s = sum[j+1] - sum[i];
            int l = -1, r = M;
            while(r-l>1){
                int x = (l+r)/2;
                if(v[p[x]]<s) l = x;
                else r = x;
            }
            L[i][j] = mx[r];
        }
        REP(i,N) dp[i] = -1;
        chmin(ans, rec(0));
    }while(next_permutation(ALL(q)));

    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}
#include<cstdio>
#include<vector>
int w[15];
struct Element{
    int l,v;
};
struct Edge{
    int v,w;
    Edge(int v,int w):v(v),w(w){}
};
std::vector<Edge>g[15];
int f[15];
Element e[100005];
int seq[15];
int vis[15];
int pos[15];
int ans = -1;
int dis[1<<10];

void dfs(int p,int n,int m){
    if(p==n+1){
        for(int i = 1; i <= n; i++){ 
            g[i].clear(), f[i] = 0;
            pos[seq[i]] = i;
        }
        for(int i = 0; i < (1<<n); i++){
            int l = n+1, r = -1;
            int mask = i;
            for(int j = 1; j <= n; j++){
                if(mask%2){
                    int p = pos[j];
                    if(l>p) l = p;
                    if(r<p) r = p;
                }
                mask /= 2;
            }
            if(l<=n && r>=1 && l<r) g[l].push_back(Edge(r,dis[i]));
        }
        for(int i = 1; i <= n; i++){
            if(f[i]<f[i-1]) f[i] = f[i-1];
            for(Edge e: g[i]){
                int j = e.v, w = e.w;
                if(f[j]<f[i]+w) f[j] = f[i]+w;
            }
        }
        if(ans==-1 || ans>f[n]) ans = f[n];
    }
    else{
        for(int i = 1; i <= n; i++){
            if(vis[i]==0){
                seq[p] = i;
                vis[i] = 1;
                dfs(p+1,n,m);
                vis[i] = 0;
            }
        } 
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int maxn = -1;
    for(int i = 1; i <= n; i++){ 
        scanf("%d",&w[i]);
        if(maxn<w[i]) maxn = w[i];
    }
    int ok = 1;
    for(int i = 1; i <= m; i++){
        scanf("%d%d",&e[i].l,&e[i].v);
        if(e[i].v<maxn) ok = 0;
    }
    if(!ok){
        printf("-1\n");
        return 0;
    }
    for(int i = 0; i < (1<<n); i++){
        int sum = 0, mask = i;
        for(int j = 1; j <= n; j++){
            if(mask%2) sum += w[j];
            mask /= 2;
        }
        dis[i] = 0;
        for(int j = 1; j <= m; j++){
            if(e[j].v<sum && dis[i]<e[j].l) dis[i] = e[j].l;
        }
    }
    dfs(1,n,m);
    printf("%d\n",ans);
    return 0;
}
