#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

#define f(i, a, b) for(int i = (a); i < (b); ++i)
#define PB push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) int((x).size())
#define dump(x) cout << #x << " = " << x << endl;

void setIO(string name = "") { 
	ios_base::sync_with_stdio(0); cin.tie(0); 
	if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin); 
		freopen((name+".out").c_str(), "w", stdout);
	}
}

void solve()
{

}

struct T{int days, mon;};
struct TT{int days, mon, val;};
struct C{int w, h;};

signed main()
{	
	setIO();

	int h, t; cin >> h >> t;
	int a, b, tot=0;
	vi days(h+1,0);
	f(i,0,h) 
	{
		cin >> days[i];
		tot +=days[i];
	}
	vector<T> ts;
	vector<TT> tts;
	f(i,0,t)
	{
		cin >> a >> b;
		ts.PB({a,b});
	}
	f(i,1,1<<t)
	{
		int len = 0;
		int cash = 0;
		f(j,0,t)
		{
			if ((1 << j) & i)
			{
				len += ts[j].days;
				cash += ts[j].mon;
			}
		}
		/*
		dump(cash);
		dump(len);
		*/
		tts.PB({len, cash, i});
	}
	sort(tts.begin(), tts.end(), [](TT &t1, TT &t2){ 
			return t1.days < t2.days ||(t1.days == t2.days && t1.mon > t2.mon);});
	// build segs
	vi segs(h+1, 0);
	stack<C> s;
	int i = 0;
	s.push({1, days[i++]});

	while(s.size())
	{
//		if(i==h) break;
//		int 
//
		int add_w = 0;
		if(i==h+1)
		{
			break;
		}
		while(s.size() && days[i] < s.top().h)
		{
			C now = s.top();
			s.pop();
			add_w += now.w;
			int next_h = days[i];
			if(s.size())
				next_h = max(next_h, s.top().h);
			segs[add_w] += now.h - next_h;
		}
		if(!s.size() ||days[i] > s.top().h)
			s.push({add_w+1, days[i++]});
		else if(days[i] == s.top().h)
		{
			s.top().w+=add_w + 1; i++;
		}
	}
	int lptr = 0;
	int rptr = 0;
	int used = 0;
	int ans = 0;
	f(i,0,segs.size())
	{
		// +1 err?
		while (rptr < tts.size() && tts[rptr].days <= i ) rptr++;
		while (segs[i] && lptr < rptr)
		{
			TT *best = nullptr;
			f(j,lptr,rptr)
			{
				if (!(tts[j].val & used))
				{
					if (best == nullptr || best->mon < tts[j].mon)
					{
						best = &tts[j];
					}
				}
			}
			ans += best->mon;
			/*
			dump(best->val);
			dump(best->mon);
			dump(best->days);
			*/
			used |= best->val;
			while(lptr < tts.size() && (tts[lptr].val & used))
			{
				lptr++;
			}
			segs[i]--;
		}
	}
	cout << ans << "\n";




  return 0;
}