// submasks taken from https://cp-algorithms.com/algebra/all-submasks.html

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef long long ll;
const ll mod = 1e18;

ll a[17], D[17], I[17], party_I[1 << 17], party_D[1 << 17];
ll dp[17][1 << 17];
ll n, t, s;
vector <ll> max_days;

ll f(ll i, ll mask) {
	if (i == t || max_days[i] == 0) return 0;
	if (dp[i][mask] != -1) return dp[i][mask];
	ll ret = -mod;
	for (ll submask = mask; submask; submask = (submask - 1) & mask) {
		if (party_D[submask] == max_days[i]) {
			ret = max(ret, party_I[submask] + f(i + 1, mask ^ submask));
		}
	}
	return dp[i][mask] = ret;
}

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

	cin >> n >> t;
	ll cnt = 0;
	for (ll i = 0; i < n; i++) {
		ll x;
		cin >> x;
		if (x > t) {
			cout << 0;

			return 0;
		}

		if (x != 0) {
			a[0] += 1;
			a[min(x, t) + 1] -= 1;
		}

		if (x == 0 || i == n - 1) {
			for (ll j = 1; j <= t; j++) {
				a[j] += a[j - 1];
				if (a[j] > 0) {
					if (++cnt > t) {
						cout << 0;
						return 0;
					}
				}
				max_days.push_back(a[j]);
			}
			memset(a, 0, sizeof a); 
		}
	}
	for (ll i = 0; i < t; i++) {
		cin >> D[i] >> I[i];
	}

	for (ll mask = 0; mask < (1 << t); mask++) {
		for (ll k = 0; k < t; k++) {
			if (mask & (1 << k)) {
				party_I[mask] += I[k];
				party_D[mask] += D[k];
			}
		}
	}

	sort(all(max_days));
	reverse(all(max_days));

	/*for (ll i = 0; i < max_days.size(); i++) {
	  cout << max_days[i] << " ";
	  }
	  cout << endl;*/

	memset(dp, -1, sizeof dp);
	ll sol = f(0, (1 << t) - 1);
	cout << (sol < 0 ? 0 : sol);
}