// Source: https://usaco.guide/general/io

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

#define vt vector
typedef long long Int;

int main() {
	int h, T; cin >> h >> T;
	vt<int> c(h);
	Int totaltime = 0;
	for(auto &x: c) {
		cin >> x;
		totaltime += x;
	}
	vt<int> d(T), inc(T);
	for(int i = 0; i < T; ++i) {
		cin >> d[i] >> inc[i];
	}
	vt<int> a;
	int minth = *min_element(d.begin(), d.end());
	for(int i = 0; i < 16; ++i) {
		for(int j = 0; j < h; ++j) if(c[j] >= i + 1) {
			int k = j;
			while(k + 1 < h && c[k+1] >= i + 1) {
				++k;
			}
			a.push_back(k - j + 1);
			if(a.back() < minth) {
				a.pop_back();
			}
			j = k;
		}
	}
	if(a.empty()) {
		cout << 0 << endl;
		return 0;
	}
	set<int> ids;
	for(auto x: d) {
		for(int i = 0, cnt = 16; i < (int)a.size() && cnt > 0; ++i) {
			if(a[i] >= x) {
				ids.insert(i);
				--cnt;
			}
		}
	}
	vt<int> b;
	for(auto i: ids) {
		b.push_back(a[i]);
	}
	vt<vt<int>> suff_pos(1 << T, vt<int>(b.size(), (int)b.size() + 1));
	vt<int> sum(1 << T, 0);
	for(int m = 1; m < (1<<T); ++m) {
		int s = 0;
		for(int i = 0; i < T; ++i) if(m >> i & 1) {
			s += d[i];
		}
		sum[m] = s;
		for(int i = 0; i < (int)b.size(); ++i) if(b[i] >= s) {
			suff_pos[m][i] = i;
		}
		for(int i = (int)b.size()-2; i >= 0; --i) {
			suff_pos[m][i] = min(suff_pos[m][i], suff_pos[m][i+1]);
		}
	}
	vt<int> dp(1 << T, (int)b.size()+1);
	dp[0] = -1;
	int res = 0;
	for(int mask = 1; mask < (1<<T); ++mask) {
		for(int submask = mask; submask; submask = (submask-1) & mask) {
			int from = mask ^ submask, pos = dp[from];
			if(pos + 1 < b.size()) {
				dp[mask] = min(dp[mask], suff_pos[submask][pos + 1]);
			}
		}
		if(dp[mask] < b.size() && sum[mask] == totaltime) {
			int tot = 0;
			for(int i = 0; i < T; ++i) if(mask >> i & 1) {
				tot += inc[i];
			}
			res = max(res, tot);
		}
	}
	cout << res << endl;
}