#pragma GCC optimize "O3"
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a; i<b; i++)
#define pb push_back
#define fi first
#define se second
#define debug(...) //fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;
typedef long double ld;

const int T = 16;
const int inf = 1e9;
int Dp[T+1][1<<T], Time[1<<T], Profit[1<<T];

int main ()
{
	//ios_base::sync_with_stdio(false);
	int h, t;
	scanf ("%d %d", &h, &t);
	
	vector <int> shops;

	
	vector <int> H(h);
	for (int &c: H) scanf ("%d", &c);
	H.pb(0);
	
	for (int c: H) if (c > t) {
		printf ("0\n");
		return 0;
	}
	
	vector <int> stan(t+1, -1); //not free
	
	int tm = 0;
	for (int c: H)
	{
		tm++;
		
		rep(i,1,t+1) {
			
			if (i <= c) {
				if (stan[i] == -1) {
					stan[i] = tm;
				}
			} else {
				
				if (stan[i] > 0) {
					shops.pb(tm - stan[i]);
					stan[i] = -1;
				}
			}
		}
	}
	
	if ((int)shops.size() > t) {
		printf ("0\n");
		return 0;
	}
	
	debug ("Shops: ");
	for (int s: shops) debug ("%d ", s);
	debug ("\n");
	
	rep(i,0,T+1) rep(j,0,(1<<T)) Dp[i][j] = -inf;
	
	Dp[0][0] = 0;
	int m = (int)shops.size();
	
	vector <pair <int, int> > Teams(t);
	for (auto &p: Teams) scanf ("%d %d", &p.fi, &p.se);
	
	rep(mask,0,(1<<t)) {
		rep(i,0,t) if (mask & (1<<i)) {
			Time[mask] += Teams[i].fi;
			Profit[mask] += Teams[i].se;
		}
	}	
	
	rep(i,1,m+1) {
		
		rep(mask,0,(1<<t)) if (Dp[i-1][mask] >= 0) {
			
			int wolne = ((1 << t) -1) ^ mask;
			
			for (int nowe = wolne; nowe > 0; nowe = (nowe - 1) & wolne) {
					
				if (Time[nowe] == shops[i-1]) {
					
					Dp[i][mask | nowe] = max(Dp[i][mask | nowe], Dp[i-1][mask] + Profit[nowe]);
				}
			}
		}
	}
	
	int best = 0;
	rep(mask,0,(1<<t)) best = max(best, Dp[m][mask]);
	
	printf ("%d\n", best);
	
}