#include<bits/stdc++.h>
#define N 100005
#define re 
#define ll long long
#define P 167772161
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
	re char c;res=0;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
}
int H,tot,u;
int w[N],a[N],Get[N],LOG[N];
int sumL[N],sumV[N];
int L[N],V[N];
void FWT(int *a,int n){
	for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){
		int x=a[i+j],y=a[i+j+d];
		a[i+j+d]=x+y;
	}
}
void IFWT(int *a,int n){
	for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){
		int x=a[i+j],y=a[i+j+d];
		a[i+j+d]=y-x;
	}
}
bool mk[25];
int f[17][70005],g[17][70005],h[17][70005];
int main(){
	Rd(H),Rd(n);u=1<<n;
	for(re int i=1;i<=H;i++){
		Rd(w[i]);
		if(w[i]>n){puts("0");return 0;}
	}
	for(re int k=1;k<=n;k++){
		int res=0;
		for(re int i=1;i<=n&&tot<=n;i++){
			if(w[i]>=k)res++;
			else if(res>0)a[++tot]=res,res=0;
		}
		if(res>0)a[++tot]=res,res=0;
		if(tot>n)break;
	}
	if(tot>n){puts("0");return 0;}
	for(re int i=1;i<=n;i++)Rd(L[i]),Rd(V[i]);
	for(re int i=1;i<u;i++)Get[i]=Get[i&(i-1)]+1;
	for(re int i=2;i<u;i++)LOG[i]=LOG[i>>1]+1;
	for(re int i=1;i<u;i++)sumL[i]=sumL[i&(i-1)]+L[LOG[i&-i]+1],sumV[i]=sumV[i&(i-1)]+V[LOG[i&-i]+1];
	
	bool flag=1;
	for(re int i=1;i<=tot;i++){
		for(re int s=0;s<u;s++)if(sumL[s]==a[i])g[Get[s]][s]=1,mk[Get[s]]=1;
		for(re int j=1;j<=n;j++)if(mk[j])FWT(g[j],u);
		
		if(flag){
			for(re int j=1;j<=n;j++){
				mk[j]=0;
				for(re int s=0;s<u;s++)f[j][s]=g[j][s],g[j][s]=0;
			}
			flag=0;
			continue;
		}
		
		for(re int j=1;j<=n;j++)
			for(re int k=1;k<=n;k++)if(mk[k])
				for(re int s=0;s<u;s++)h[j+k][s]+=f[j][s]*g[k][s];
		
		for(re int j=1;j<=n;j++){
			mk[j]=0;
			for(re int s=0;s<u;s++)f[j][s]=h[j][s],h[j][s]=0,g[j][s]=0;
		}
	}
	for(re int i=1;i<=n;i++)IFWT(f[i],u);
	int res=0;
	for(re int i=1;i<=n;i++)
		for(re int s=0;s<u;s++)
			if(Get[s]==i&&f[i][s]!=0)res=max(res,sumV[s]);
	printf("%d\n",res);
	return 0;
}