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

#define REP(i, n) for(int i = 0; i < (n); i++)
typedef long long int ll;

const int inf = 1e9;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, t;
	cin >> n >> t;
	vector <int> svi(n);
	REP(i, n) cin >> svi[i];
	vector <int> najveci(t, 0);
	for(int i = 1; i <= t; i++) {
		int br = 0;
		REP(j, n) {
			if(svi[j] < i) {
				if(br) najveci.push_back(br);
				br = 0;
			}
			else br++;
		}
		if(br) najveci.push_back(br);
	}
	sort(najveci.begin(), najveci.end());
	reverse(najveci.begin(), najveci.end());
	vector <pair <int, int> > pom;
	vector <int> maske;
	REP(i, (1 << t)) pom.push_back(make_pair(__builtin_popcount(i), i));
	sort(pom.begin(), pom.end());
	REP(i, (int)pom.size()) maske.push_back(pom[i].second);
	//
	vector <int> pojvel(t), pojvr(t);
	REP(i, t) cin >> pojvel[i] >> pojvr[i];
	//
	vector <int> vel, vr;
	REP(i, (1 << t)) {
		int trvel = 0, trvr = 0;
		REP(j, t) {
			if(i & (1 << j)) {
				trvel += pojvel[j];
				trvr += pojvr[j];
			}
		}
		vel.push_back(trvel);
		vr.push_back(trvr);
	}
	//
	vector <int> maksivel((1 << t), 0), novimaksivel;
	REP(i, t) {
		novimaksivel.clear();
		novimaksivel.resize((1 << t), 0);
		REP(j, (1 << t)) {
			if(najveci[i] >= vel[j] - maksivel[j]) {
				novimaksivel[j] = vel[j];
			}
		}
		for(int j : maske) {
			int maksi = novimaksivel[j];
			REP(k, t) {
				if(j & (1 << k)) {
					maksi = max(maksi, novimaksivel[j & (~(1 << k))]);
				}
			}
			maksivel[j] = maksi;
		}
	}
	int rj = 0;
	REP(i, (1 << t)) {
		if(maksivel[i] == vel[i]) rj = max(rj, vr[i]);
	}
	cout << rj << "\n";
	return 0;
}