#include<bits/stdc++.h>
#define ll long long 
#define N 100005
#define P 167772161
#define GC getchar()
#define PC putchar
using namespace std;
ll re(){
	ll s=0,b=1; char c=GC;
	while(c>'9'||c<'0'){if(c=='-')b=-b; c=GC;}
	while(c<='9'&&c>='0'){s=(s<<1)+(s<<3)+(c^48); c=GC;}
	return s*b;
}
void ks(ll s){if(s<0)PC('-'),s=-s; if(s>=10)ks(s/10); PC((s%10)|48);}
int n,m,h[N],a[N],s,cd[17],jz[17],su[1<<16],sjz[1<<16],an;
bool dp[17][1<<16];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	n=re(),m=re();
	for(int i=1; i<=n; ++i){
		h[i]=re();
		if(h[i]>m){
			ks(0);
			return 0;
		}
	}
	for(int i=1; i<=n; ++i){
		while(h[i]){
			int le=0,j=i;
			while(h[j]&&j<=n){
				h[j]--; j++; le++;
			}
			q.push(le);
			if(q.size()>m) {
				ks(0);
				q.pop();
				return 0;
			}
		}
	}
	while(!q.empty()){a[++s]=q.top(); q.pop();}
	for(int i=0; i<m; ++i){cd[i]=re(); jz[i]=re();}
	for(int i=1; i<(1<<m); ++i)
	 for(int j=0; j<m; ++j)
	  if(i&(1<<j)){su[i]=su[i^(1<<j)]+cd[j]; sjz[i]=sjz[i^(1<<j)]+jz[j]; break;}
	dp[0][0]=1;
	for(int i=1; i<=s; ++i){
		for(int j=0; j<(1<<m); ++j){
			if(!dp[i-1][j])continue;
			int os=((1<<m)-1)^j; //dp[i][j]=1;
			for(int k=os; k; k=(k-1)&os)
			 if(su[k]==a[i])dp[i][j|k]=1;
		}
		//for(int j=0; j<(1<<m); ++j)cout<<dp[i][j]; cout<<endl;
	}
	for(int i=0; i<(1<<m); ++i)
	 if(dp[s][i])an=max(an,sjz[i]);
	ks(an);
}