#include <bits/stdc++.h>

using namespace std;

#define ALL(x) (x).begin(), (x).end()

template<class C> void mini(C &a5, C b5) { a5 = min(a5, b5); }
template<class C> void maxi(C &a5, C b5) { a5 = max(a5, b5); }

#ifdef LOCAL
const bool debug = true;
#else
const bool debug = false;
#define cerr if (true) {} else cout
#endif

//#define int long long
//#define double long double

//const int INF = 1e18;
//const int mod = 1e9 + 7;

const int nax = 16;

bool czy[nax][1 << nax];
bool  dp[nax][1 << nax];

int ck[1000000];
vector<int> plecaki;

int len[100], cost[100];

int pot(int n, int k) {
	int res = 1;
	while (k--) {
		res *= n;
	}
	return res;
}

vector<int> submaski[1 << nax];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int h, t;
    cin >> h >> t;
    
    for (int i = 0; i < h; i++) {
		cin >> ck[i];
		if (ck[i] > t) {
			cout << 0 << endl;
			cerr << "xd1";
			return 0;
		}
	}
	
	for (int i = 1; i <= t; i++) {
		int dl = 0;
		for (int j = 0; j <= h; j++) {
			if (ck[j] >= i) {
				dl++;
			} else {
				if (dl)
					plecaki.push_back(dl);
				dl = 0;
			}
		}
	}
	
	//while ((int)plecaki.size() < 20) plecaki.push_back(0);
	
	sort(ALL(plecaki));
	reverse(ALL(plecaki));
	if ((int)plecaki.size() > t) {
		cout << 0 << endl;
			cerr << "xd2";
		return 0;
	}
	plecaki.resize(t);
	
	for (int i = 0; i < t; i++) {
		cin >> len[i] >> cost[i];
	}
	
	for (int i = 0; i < t; i++) {
		//czy[i][0] = true;
		for (int mask = 0; mask < (1 << t); mask++) {
			int len_sum = 0;
			for (int j = 0; j < t; j++) {
				if (mask & (1 << j)) {
					len_sum += len[j];
				}
			}
			if (len_sum == plecaki[i]) {
				czy[i][mask] = true;
			}
		}
	}
	
	for (int _mask3 = 0; _mask3 < pot(3, t); _mask3++) {
		int mask = 0, mask2 = 0, mask3 = _mask3;
		for (int i = 0; i < t; i++) {
			int x = mask3 % 3;
			mask *= 2;
			mask2 *= 2;
			if (x == 1) mask++;
			if (x >= 1) mask2++;
			mask3 /= 3;
		}
		submaski[mask2].push_back(mask);
	}
	
	for (int mask = 0; mask < (1 << t); mask++) {
		dp[0][mask] = czy[0][mask];
	}
	
	for (int i = 1; i < t; i++) {
		//dp[i][0] = true;
		
		for (int mask = 0; mask < (1 << t); mask++) {
			for (int submask : submaski[mask]) {
				dp[i][mask] |= dp[i - 1][submask] && czy[i][mask ^ submask];
			}
		}
	}
	
	long long res = 0;
	for (int mask = 0; mask < (1 << t); mask++) {
		if (dp[t - 1][mask]) {
			long long cur = 0;
			for (int i = 0; i < t; i++) {
				if (mask & (1 << i)) {
					cur += cost[i];
				}
			}
			maxi(res, cur);
		}
	}
	
	cout << res << "\n";
    
    return 0;
}/*
3 4
2 1 2
3 2
1 1
1 2
1 3
* 
4 7
2 2 1 1
3 1
1 1
1 4
1 1
2 4
2 2
2 1
* 
3 16
100 4 100
1 1
1 1
1 1
3 1
1 1
1 1
3 1
1 1
3 1
1 1
1 1
2 1
1 1
2 1
1 1
1 1
* 15
* 
8 5
1 1 1 1 0 1 1 1
2 50
2 50
3 50
1 1
1 1
* 150
*/