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

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

vector<int> res;
vector<int> sum,len;

void solve(vector<int>& p, int n) {
	for(int i=0;i<(1<<n);i++)
		res[i] = -1;
	res[0] = 0;

	for(int m=1;m<(1<<n);m++) {
		int n = 0;
		do {
			int M = m&(~n);
			int nr = res[M];
			if(nr < p.size())
				if(len[n] == p[nr]) res[m] = nr+1;
			n=(n+1+~m)&m;
		} while(n != 0);
	}
}

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

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

	res.resize(1<<t);
	sum.assign(1<<t,0);
	len.assign(1<<t,0);

	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;
			}
	}

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

	solve(p,t);

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

	cout << R << "\n";

	return 0;
}