#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i)
#define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i)
#define ll LL
#define st f
#define nd s
#define pb PB
#define mp MP
#define eb emplace_back
#define siz(c) SIZ(c)
const int inf = 1e9+7;
const ll INF = 1e18L+7;

#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type 
{int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if(p>y) p = y;}
sim, class s> void maxi(n &p, s y) {if(p<y) p = y;}
#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif 

#define I(x) #x " =", (x), " "

#ifndef LOCAL
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template <typename T>
using ordered_set =
	tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#else
#include</Users/dawid/algo/mac/ordered_set>
#endif

const int T = 16;
const int N = 1e5 + 7;

int n, t;

int h[N];

int len[N];
int in[N];

int dp[T + 7][1 << T];

int sum_in[1 << T];
int sum_len[1<< T];

VI segs;

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

	cin >> n >> t;

	for (int i = 1; i <= n; ++i) {
		cin >> h[i];
	}

	REP(i, t)
		cin >> len[i] >> in[i];

	REP(s, (1<<t)) REP(i, t) {
		if (s & (1 << i)) {
			sum_in[s] += in[i];
			sum_len[s] += len[i];
		}
	}

	while (siz(segs) <= t) {
		int mx = 0;

		for (int i = 1; i <= n; ++i) {
			maxi(mx, h[i]);
		}

		if (mx == 0)
			break;

		int curr = 0;

		for (int i = 1; i <= n; ++i) {
			if (h[i] == mx) {
				++curr;
				--h[i];
			} else {
				if (curr) {
					segs.pb(curr);
					curr = 0;
				}
			}
		}

		if (curr)
			segs.pb(curr);
	}

	if (siz(segs) > t) {
		cout << 0 << endl;
		return 0;
	}

	for (int i = 0; i <= T; ++i) {
		REP(j, (1<<T))
			dp[i][j] = -inf;
	}

	debug(segs);

	debug(sum_in[(1<<t)-1]);
	debug(sum_len[(1<<t)-1]);

	int s = siz(segs);
	int subs = (1<<t);

	dp[0][0] = 0;

	for (int i = 1; i <= s; ++i) {
		for (int a = 1; a < subs; ++a) {
			for (int b = a; b; b = a&(b-1)) {
				if (sum_len[b] == segs[i - 1])
					maxi(dp[i][a], sum_in[b] + dp[i - 1][a ^ b]);
			}

			debug(I(i), I(a), I(dp[i][a]));
		}
	}

	int ans = 0;

	REP(i, (1<<t))
		maxi(ans, dp[s][i]);

	cout << ans << endl;
}