#include <bits/stdc++.h>

using namespace std;

const int INF = (1 << 28);
unordered_map <long long, int> m;
vector <pair <int, int> > p;
int h, t;
vector <int> v;
int d;

int f(int mask, int val, int id) {
	if (id == d) {
		return 0;
	}
	if (val == 0) {
		return f(mask, v[id + 1], id + 1);
	}
	const long long vv = ((long long)val << 25) + ((long long)id << 18) + mask;
	if (m.find(vv) != m.end()) {
		return m[vv];
	}
	int ans = -INF;
	for (int i = 0; i < t; ++i) {
		if ((mask & (1 << i)) == 0) {
			continue;
		}
		if (val >= p[i].first) {
			ans = max(ans,
				f(mask ^ (1 << i), val - p[i].first, id) + p[i].second);
		}
	}
	m[vv] = ans;
	return ans;
}

void solve() {
	scanf("%d%d", &h, &t);
	vector <int> c;
	int ma = 0;
	for (int i = 0; i < h; ++i) {
		int x;
		scanf("%d", &x);
		c.push_back(x);
		ma = max(ma, x);
	}
	if (ma > 16) {
		printf("0\n");
		return;
	}
	int len;
	for (int i = 1; i <= 16; ++i) {
		len = 0;
		for (int j = 0; j < h; ++j) {
			if (c[j] < i) {
				if (len > 0) {
					v.push_back(len);
				}
				len = 0;
			}
			else {
				++len;
			}
		}
		if (len > 0) {
			v.push_back(len);
		}
	}
	d = v.size();
	//int sum = 0;
	//for (auto xd : v) {
		//sum += xd;
	//}
	for (int i = 0; i < t; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		p.push_back({a, b});
	}
	int ans = f((1 << t) - 1, v[0], 0);
	if (ans < 0) {
		ans = 0;
	}
	printf("%d\n", ans);
}

int main() {
	int tt = 1;
	//scanf("%d", &tt);
	for (int ii = 0; ii < tt; ++ii) {
		solve();
	}
	return 0;
}