#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // Poland
using LL = long long; 
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int ssize(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

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

	int h, t;
	cin >> h >> t;
	vector<int> c(h);
	for(int &ci : c)
		cin >> ci;
	vector<pair<int, int>> oper(t);
	for(auto &p : oper)
		cin >> p.first >> p.second;
	debug(h, t, c, oper);

	LL sum_ci = accumulate(c.begin(), c.end(), 0LL);
	LL sum_oper = 0;
	for(auto &p : oper)
		sum_oper += p.first;

	if(sum_ci > sum_oper) {
		cout << "0\n";
		return 0;
	}

	for(int &ci : c)
		if(ci > t) {
			cout << "0\n";
			return 0;
		}
	assert(*min_element(c.begin(), c.end()) <= t);

	vector<int> all_strips;
	for(int i = 0; i < t; ++i) {
		vector<bool> is_lit(h);
		REP(day, h)
			if(c[day] >= i + 1)
				is_lit[day] = true;
		debug(i, is_lit);

		vector<int> strips;
		for(int l = 0; l < h; ++l)
			if(is_lit[l]) {
				int r = l;
				while(r + 1 < h and is_lit[r + 1])
					++r;
				debug(i, l, r);
				strips.emplace_back(r - l + 1);
				l = r;
			}
		debug(i, strips);
		
		for(int strip : strips)
			all_strips.emplace_back(strip);
	}
	debug(all_strips);

	if(ssize(all_strips) > t) {
		cout << "0\n";
		return 0;
	}
	assert(ssize(all_strips) <= t);

	vector<int> sum_lengths_subset(1 << t);
	REP(mask, 1 << t)
		REP(i, t)
			if((mask >> i) & 1)
				sum_lengths_subset[mask] += oper[i].first;
	debug(sum_lengths_subset);

	vector<vector<bool>> dp(ssize(all_strips) + 1, vector<bool>(1 << t));
	dp[0][0] = true;
	FOR(prefix, 1, ssize(all_strips)) {
		REP(mask, 1 << t)
			if(not dp[prefix][mask])
				for(int submask = mask; submask > 0; submask = ((submask - 1) & mask))
					if(sum_lengths_subset[submask] == all_strips[prefix - 1] and dp[prefix - 1][mask ^ submask])
						dp[prefix][mask] = true;
		debug(prefix, dp[prefix]);
	}

	int answer = 0;
	REP(mask, 1 << t)
		if(dp.back()[mask]) {
			int local_ans = 0;
			REP(i, t)
				if((mask >> i) & 1)
					local_ans += oper[i].second;
			debug(mask, local_ans);
			answer = max(answer, local_ans);
		}
	cout << answer << '\n';
}