#include <bits/stdc++.h>

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef pair<LL,LL> PLL;
typedef vector < int > VI;

const int MT = 17, MM = (1 << 16) +  5, MH = 100005, inf = 1000000005, mod = 1000000007;
const LL INF = 1000000000000000005LL;

int dp[MT][MM];
int C[MH], D[MT], I[MT];
int zysk[MM], czas[MM];

int main()
{
	int h, t, ans = 0;
	scanf("%d%d", &h, &t);
	for(int i = 1; i <= h; ++i)
	{
		scanf("%d", &C[i]);
		if(C[i] > t)
		{
			printf("0");
			return 0;
		}
	}
	VI V;
	for(int i = 1; i <= t; ++i)
	{
		int len = 0;
		for(int j = 1; j <= h; ++j)
		{
			if(C[j] < i)
			{
				if(len)
					V.pb(len);
				len = 0;
			}
			else
			{
				++len;
			}
		}
		if(len)
			V.pb(len);
	}
	int N = V.size();
	if(N > t)
	{
		printf("0");
		return 0;
	}
	/*for(auto v : V)
		printf("%d ", v);
	printf("\n");*/
	for(int i = 0; i < t; ++i)
		scanf("%d%d", &D[i], &I[i]);
	int T = (1 << t);
	for(int i = 1; i < T; ++i)
		for(int j = 0; j < t; ++j)
			if((i >> j) & 1)
			{
				czas[i] = czas[i - (1 << j)] + D[j];
				zysk[i] = zysk[i - (1 << j)] + I[j];
				//printf("%d %d %d\n", i, czas[i], zysk[i]); 
				break;
				//if(czas[i] <= h)
				//	kto[czas[i]].pb(i);
			}
	dp[0][0] = 1;
	for(int i = 1; i <= N; ++i)
		for(int j = 0; j < T; ++j)
			for(int k = j; k > 0; k = (k - 1) & j)
			{
				if(czas[k] == V[i - 1] && dp[i - 1][j - k])
				{
					dp[i][j] = 1;
				}
			}
	for(int mask = 0; mask < T; ++mask)
		if(dp[N][mask])
			ans = max(ans, zysk[mask]);
	printf("%d", ans);
	
	
}