#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int maxn = 3e5;
const int inf = 0x3f3f3f3f;

struct B{
	int l, v;
}p[maxn];
int N, M, Min[maxn], w[15], temp_w[15], sum[15], used[15];
int d[15][15], dis[15], Minw, ans, vis[15];

bool operator < (const  B& a,const B& b){
	return a.l < b.l;
} 
void init(){
	cin >> N >> M;
	Minw = inf;
	ans = inf;
	for(int i = 1; i <= N; ++i) cin >> w[i];
	for(int i = 1; i <= M; ++i){
		cin >> p[i].l >> p[i].v;
		Minw = min(Minw, p[i].v);
	}
	sort(p + 1, p + 1 + M);
	Min[M] = p[M].v;
	for(int i = M - 1; i >= 1; --i){
		Min[i] = min(Min[i + 1], p[i].v);
	}
}

int bin_search(int x){
	int l = 1, r = M + 1;
	while (l < r){
		int mid = (l + r) >> 1;
		if(Min[mid] < x) l = mid + 1;
		else r = mid;
	}
	return p[l - 1].l;
}
int Caculate() {
	for(int i = 1; i <= N; ++i){
		sum[i] = temp_w[i] + sum[i - 1];
	}
	memset(dis, 0, sizeof(dis));
	for(int i = 1; i <= N; ++i){
		for(int j = i + 1; j <= N; ++j){
			dis[j] = max(dis[i] +  bin_search(sum[j] - sum[i - 1]), dis[j]);
		}
	}
	return dis[N];
}


void dfs(int cnt){
	if(cnt == N + 1){
		ans = min(ans, Caculate());
		return;
	}
	for(int i = 1; i <= N; ++i){
		if(!vis[i]){
			vis[i] = 1;
			temp_w[cnt] = w[i]; 
			dfs(cnt + 1);
			vis[i] = 0;	
		}
	}
}

signed main(){
	init();
	for(int i = 1; i <= N; ++i){
		if(w[i] > Minw){
			cout << -1;
			return 0;
		}
	}
	dfs(1);
	cout << ans;
	return 0;
}
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int inf = 1e15 + 5 ; 
const int N = 10 ; 
const int M = 1e5 + 5 ; 
int n, w[N], Id[N], b[N], f[N], m ; 
struct node {
	int l, v ; 
	node(int _l = 0, int _v = 0) { l = _l, v = _v ; }
	bool operator < ( const node &x ) const {
		return (l == x.l) ? v > x.v : l < x.l ;  
	} 
} l[M] ;
set<node> S ; 
set<node>::iterator it ; 
signed main()
{
	n = gi(), m = gi() ; int mx = 0, mi = inf ; 
	rep( i, 1, n ) w[i] = gi(), Id[i] = i, mx = max(mx, w[i]) ;
	rep( i, 1, m ) l[i].v = gi(), l[i].l = gi(), mi = min( mi, l[i].l ) ;
	if( mx > mi ) { puts("-1") ; exit(0) ; }
	sort(l + 1, l + m + 1) ; 
	S.insert(node(-1, 0)), S.insert(l[1]) ; 
	rep( i, 2, m ) l[i].v = max( l[i - 1].v, l[i].v ) ; 
	rep( i, 2, m ) S.insert(l[i]) ; 
	int Ans = inf ; 
	do {
		b[0] = 0 ; 
		rep( i, 1, n ) b[i] = w[Id[i]] ; 
		rep( i, 1, n ) b[i] += b[i - 1] ; 
		rep( i, 1, n ) f[i] = 0 ; 
		rep( i, 2, n ) {
			f[i] = f[i - 1] ; 
			rep( j, 1, i - 1 ) {
				it = S.upper_bound(node(b[i] - b[j - 1], inf)) ; 
				-- it ; node u = *it ; 
				f[i] = max( f[i], f[j] + u.v ) ; 
			}
		}
		Ans = min( Ans, f[n] ) ; 
	} while(next_permutation(Id + 1, Id + n + 1)) ;
	cout << Ans << endl ; 
	return 0 ;
}