#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
int D_RECUR_DEPTH = 0;
#define deb(x) {++D_RECUR_DEPTH; auto x2=x; --D_RECUR_DEPTH; cerr<<string(D_RECUR_DEPTH, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x2<<"\e[39m"<<endl;}
template<typename O, typename C> typename enable_if<is_same<O,ostream>::value, O&>::type operator<<(O& ost,  const C& v){if(&ost == &cout) {cerr<<"Warning, printing debugs on cout!"<<endl;} ost<<"["; bool firstIter = true; for(auto& x:v){ if(firstIter) firstIter = false; else ost<<", "; ost<<x;} return ost<<"]";}
template<typename Ostream, typename ...Ts>Ostream& operator<<(Ostream& ost,  const pair<Ts...>& p){if(&ost == &cout) {cerr<<"Warning, printing debugs [pair] on cout!"<<endl;}return ost<<"{"<<p.first<<", "<<p.second<<"}";}
#else
#define deb(x)
#endif

template<class C> C reversed(C c) {reverse(c.begin(),c.end()); return c;}
#define mp make_pair
#define st first
#define nd second
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 16;
int dp[17][1<<MAXN];
int zsum[1<<MAXN];
int zlen[1<<MAXN];

int32_t main(){
    ios::sync_with_stdio(false);
    int n,t;
    cin >> n >> t;
    vector<int> segs;
    vector<int> len(20);

    vector<int> tab(n);
    for(int i=0;i<n;i++)
        cin >> tab[i];
    tab.push_back(0);

    for(auto x:tab) {
        if(x >= 19) {
            cout<<"0\n";
            return 0;
        }
        for(int j=0;j<x;j++)
            len[j]++;
        for(int j=x;j<20;j++) {
            if(len[j] > 0)
                segs.push_back(len[j]);
            len[j] = 0;
        }
        if(segs.size() > 16) {
            cout<<"0\n";
            return 0;
        }
    }
   // deb(segs);
    vector<pair<int,int> > zl(t);
    for(int i=0;i<t;i++) 
        cin >> zl[i].st >> zl[i].nd;
    
    n = segs.size();
    for(int i=0;i<(1<<t);i++) {
        int sum = 0,llen=0;
        for(int j=0;j<t;j++)
            if(i&(1<<j)) {
                llen += zl[j].st;
                sum += zl[j].nd;
            }
        zsum[i] = sum;
        zlen[i] = llen;
    }

    dp[0][0] = 1;
    for(int i=1;i<=segs.size();i++) {
        for(int M=0;M<(1<<t);M++) {
            int x=0; 
            do {
                int m2 = M^x;
                if(zlen[x] == segs[i-1]) {
                    dp[i][M] |= dp[i-1][m2];
                  //  if(dp[i-1][m2])
                       // cout<<bitset<7>(x)<<" "<<zlen[x]<<" "<<bitset<7>(m2)<<" "<<dp[i-1][endl;
                }
                x=(x+1+~M)&M; 
            } while (x!=0);
           // cout<<i<<" "<<bitset<7>(M)<<" "<<dp[i][M]<<endl;
        }

    }
    int res = 0;
    for(int M=0;M<(1<<t);M++)
        if(dp[segs.size()][M]) {
            res = max(res, zsum[M]);
           // cout<<bitset<7>(M)<<endl;
        }
    cout<<res<<"\n";


}