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

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

pair<int,int> res[1<<MAXT];
int sum[1<<MAXT];

void solve(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();
	vector<vector<int>> nxt(n,vector<int>(len,inf));
	for(int i=0;i<n;i++) {
		nxt[i][len-1] = inf;
		for(int j=len-2;j>=0;j--)
			nxt[i][j] = (p[j+1] >= 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;

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

	vector<int> p;
	for(int i=0;i<t;i++) {
		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(p,D);

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

	int R = 0;
	for(int i=0;i<(1<<t);i++)
		if(res[i].first < p.size())
			R = max(R, sum[i]);

	cout << R << "\n";

	return 0;
}