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

const int MAXH = 1e5;
const int MAXT = 16;
const int inf = 1e9;

pair<int,int> dp[MAXT][1<<MAXT];
bool res[MAXT][1<<MAXT];
int nxt[MAXT][MAXH+1];
int sum[1<<MAXT];

void solve(pair<int,int>* res, vector<int>& p, vector<int>& D) {
	int n = D.size();
	for(int i=0;i<(1<<n);i++)
		res[i] = {inf,inf};
	res[0] = {0,0};

	int len = p.size();
	for(int i=0;i<n;i++) {
		nxt[i][len] = inf;
		for(int j=len-1;j>=0;j--)
			nxt[i][j] = (p[j] >= D[i] ? (j+1 >= p.size() ? inf : j+1) : nxt[i][j+1]);
	}

	for(int m=1;m<(1<<n);m++)
		for(int v=0;v<n;v++)
			if(m&(1<<v)) {
				int M = m^(1<<v);
				int x,y;
				tie(x,y) = res[M];
				if(x >= p.size())
					continue;
				if(D[v]+y <= p[x])
					res[m] = min(res[m], make_pair(x,D[v]+y));
				else
					res[m] = min(res[m], make_pair(nxt[v][x],D[v]));
			}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int h,t;
	cin >> h >> t;

	vector<int> c(h);
	for(int& i : c)
		cin >> i, i = min(i,t);

	vector<int> D(t),I(t);
	for(int i=0;i<t;i++)
		cin >> D[i] >> I[i];

	for(int i=0;i<t;i++) {
		vector<int> p;
		int last = -2;
		for(int j=0;j<h;j++)
			if(c[j] >= i+1) {
				if(last+1 != j) p.push_back(0);
				p.back()++;
				last = j;
			}

		solve(dp[i],p,D);
	}

	for(int m=0;m<(1<<t);m++) {
		sum[m] = 0;
		for(int i=0;i<t;i++)
			if(m&(1<<i))
				sum[m] += I[i];
	}

	for(int i=0;i<(1<<t);i++)
		if(dp[0][i].first != inf)
			res[0][i] = true;

	int R = 0;
	for(int i=1;i<t;i++)
		for(int m=0;m<(1<<t);m++) {
			int n = 0;
			do {
				if(res[i-1][n] && dp[i][m^n].first != inf) res[i][m] = true;
				n=(n+1+~m)&m;
			} while (n != 0 && !res[i][m]);
			if(res[i][m]) R = max(R, sum[m]);
		}

	cout << R << "\n";

	return 0;
}