#include <cmath>
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define un unsigned
#define ul unsigned long long
#define ll long long
#define ld long double
#define vec vector
#define mp make_pair
#define aa first
#define bb second
#define pul pair<ul, ul>
#define pll pair<ll, ll>
#define in(v, c) ((c).find(v) != (c).end())
#define F(i, n) for(ll i = 0; i < (n); i++)
#define Fun(i, n) for(ul i = 0; i < (n); i++)
#ifdef GPP_DEBUG
void __log(ostream&os){}
template<typename F,typename...R>void __log(ostream&os,F&&f,R&&...r){os<<' '<<forward<F>(f);__log(os,forward<R>(r)...);}
template<typename F,typename...R>void lout(F&&f,R&&...r){cout<<forward<F>(f);__log(cout,forward<R>(r)...);cout<<endl;}
template<typename F,typename...R>void lerr(F&&f,R&&...r){cerr<<forward<F>(f);__log(cerr,forward<R>(r)...);cerr<<endl;}
template<typename A,typename B>ostream& operator<<(ostream&os,const pair<A,B>&p) {return os<<p.aa<<' '<<p.bb;}
#else
#define lout(...)
#define lerr(...)
#endif

vec<pll> items; // weight, profit
vec<ll> bags; // size

// dp[přihrádka na kterou se dívám][maska zbylejch věcí] = nejlepší cena
// // iterates over all submasks of mask m
// for(int s=m;s>=0;s=(s-1)&m){
//     if(s==0)break;
// }

array<array<ll, 1<<16>, 16> dp;

ll dyn(ll curBag, uint16_t remItems);

ll dyn2(ll curBag, uint16_t remItems) {
	lout("dyn in", curBag, remItems);
	ll res = dyn(curBag, remItems);
	lout("dyn out", curBag, remItems, res);
	return res;
}

ll dyn(ll curBag, uint16_t remItems) {
	if(curBag >= bags.size())
		return 0;
	if(dp[curBag][remItems] != -1)
		return dp[curBag][remItems];
	ll m = -2;
	for(uint16_t s=remItems;s>=0;s=(s-1)&remItems){
    	if(s==0)break;

    	// můžu věci _s_ dát do tašky _curBag_?
    	ll weightSum = 0, profitSum = 0;
    	F(b, 16) {
    		if(s&(1<<b)) { // b-tá věc je v _s_
    			weightSum += items[b].aa;
    			profitSum += items[b].bb;
    		}
    	}
    	if(weightSum != bags[curBag]) // -> nemůžu
    		continue;

    	lout("put", s, "into", curBag, "w", weightSum);

    	// teď odeberu z remItems subset v s a pokračuji v dynamice
    	ll r = dyn2(curBag+1, remItems & (~s));
    	if(r < 0) // impossible
    		continue;
    	m = max(m, profitSum + r);
 	}
 	dp[curBag][remItems] = m;
 	return m;
}

ll solveKnapsack() {
	sort(bags.begin(), bags.end());
	for(auto & a : dp)
		fill(a.begin(), a.end(), -1);

	uint16_t allItems = (1<<items.size())-1;
	// lout("allItems", allItems);
	return max(0ll, dyn2(0, allItems));

	// ll m = -1;
	// F(curBag, bags.size())
	// 	m = max(m, dyn(curBag, allItems));
	// return max(m, 0ll);
}

int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); cout << setprecision(9) << fixed; lerr("ready");

	ll h, t;
	cin >> h >> t;
	vec<ll> arr(h);
	ll maxC = 0;
	F(i, h) {
		cin >> arr[i];
		maxC = max(maxC, arr[i]);
	}
	F(i, t) {
		ll w, p;
		cin >> w >> p;
		items.push_back(mp(w, p));
	}

	for(ll i = 1; i <= maxC; i++) { // collect stores on level i
		ll sz = 0;
		F(j, h) {
			if(arr[j] >= i) {
				sz++;
			} else if(sz > 0) {
				bags.push_back(sz);
				sz = 0;
			}
		}
		if(sz > 0)
			bags.push_back(sz);

		if(bags.size() > t) {
			cout << 0 << endl;
			return 0;
		}
	}

	lout("items");
	for(auto itm : items)
		lout(itm.aa, itm.bb);
	lout("bags");
	for(auto b : bags)
		lout(b);

	lout("res");
	cout << solveKnapsack() << endl;

	return 0;
}