#include"bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(),(x).end()
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m,i,j;
	cin>>m>>n;
	vector<int> a(m);
	vector<int> len;
	function<void(int,int)> dfs=[&](int l,int r)
		{
			if (l>=r||len.size()>n) return;
			len.push_back(r-l);
			int i;
			for (i=l; i<r; i++) --a[i];
			for (i=l; i<r; i++) if (a[i])
			{
				l=i;
				while (i<r&&a[i]) ++i;
				dfs(l,i);
				l=i;
			}
		};
	for (int &x:a) cin>>x;
	{
		int l=0,r=m;
		for (int i=l; i<r; i++) if (a[i])
		{
			l=i;
			while (i<r&&a[i]) ++i;
			dfs(l,i);
			l=i;
		}
	}
	if (len.size()>n)
	{
		cout<<"0\n";
		return 0;
	}
	vector<int> l(n),w(n);
	for (i=0; i<n; i++) cin>>l[i]>>w[i];
	m=1<<n;
	vector<int> f(m,-1e9);
	f[0]=0;
	vector<int> s1(m),s2(m);
	for (i=0; i<m; i++) for (j=0; j<n; j++)
	{
		s1[i]+=(i>>j&1)*l[j];
		s2[i]+=(i>>j&1)*w[j];
	}
	for (int x:len)
	{
		// cerr<<x<<endl;
		vector<int> g(m,-1e9);
		for (i=0; i<m; i++) for (j=i; j; j=j-1&i) if (s1[j]==x) cmax(g[i],f[i^j]+s2[j]);
		swap(f,g);
	}
	cout<<max(0,*max_element(all(f)))<<endl;
}