#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#ifdef LOC
#include "debuglib.h"
#else
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   Vi         = vector<int>;
using   Pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

int uplg(int n) { return 32-__builtin_clz(n); }
int uplg(ll n)  { return 64-__builtin_clzll(n); }

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(18);

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

	Vi labs(h);
	each(l, labs) cin >> l;

	Vi len(t), income(t);
	rep(i, 0, t) cin >> len[i] >> income[i];

	int mx = *max_element(all(labs));
	if (mx > t) {
		cout << "0\n";
		return 0;
	}

	Vi parts;
	rep(i, 0, mx) {
		int last = -1;
		rep(j, 0, h) {
			if (labs[j] <= i) {
				if (j-last-1 > 0) parts.pb(j-last-1);
				last = j;
			}
		}
		if (h-last-1 > 0) parts.pb(h-last-1);
	}

	if (sz(parts) > t) {
		cout << "0\n";
		return 0;
	}

	Vi sLen(1<<t), sIncome(1<<t);

	rep(i, 0, 1<<t) {
		rep(j, 0, t) {
			if ((i>>j) & 1) {
				sLen[i] += len[j];
				sIncome[i] += income[j];
			}
		}
	}

	//deb(len, income, parts, sLen, sIncome);

	Vi prv(1<<t, -1e9), cur(1<<t, -1e9);
	cur[0] = 0;

	each(p, parts) {
		prv.swap(cur);
		cur.assign(1<<t, -1e9);
		rep(i, 0, 1<<t) {
			for (int j = i; j; j = (j-1) & i) {
				if (sLen[j] == p) {
					cur[i] = max(cur[i], prv[i^j] + sIncome[j]);
				}
			}
		}
		//deb(prv, cur);
	}

	int ans = *max_element(all(cur));
	cout << ans << '\n';
	return 0;
}