#include<bits/stdc++.h>
using namespace std;
int a[1<<16],b[1<<16];
int f[1<<16],g[1<<16];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int cur=0;
    vector<int>q;
    vector<int>t;
    for(int day=1;day<=n;day++){
        int x;
     //   cout<<"day "<<day<<endl;
        scanf("%d",&x);
        if(cur<x){
            for(int i=cur+1;i<=x;i++)q.push_back(day);
        }
        else if(cur>x){
            while(q.size()>x){
                int y=q.back();
                q.pop_back();
                t.push_back(day-y);
      //          cout<<"in "<<y<<endl;
                if(q.size()>m){
                    assert(0);
                }
            }
        }
        cur=x;
    }
    while(!q.empty()){
        t.push_back(n-q.back()+1);
        
    //    cout<<"in "<<n-q.back()+1<<endl;
        q.pop_back();
    }
    for(int i=0;i<m;i++){
        scanf("%d%d",&a[1<<i],&b[1<<i]);
    }
    for(int i=0;i<(1<<m);i++){
        for(int j=0;j<m;j++){
            if(i>>j&1&&i!=(1<<j))a[i]+=a[1<<j],b[i]+=b[1<<j];
        }
    //    cout<<a[i]<<" "<<b[i]<<endl;
    }
    int ans=0;

    for(int i=0;i<t.size();i++){
        memcpy(g,f,sizeof(f));
     //   cout<<i<<' '<<t[i]<<endl;
        for(int u=1;u<(1<<m);u++){
            for(int s=u; s>0; s=(s-1)&u){
                if(a[u^s]==t[i]){
         //           cout<<(u^s)<<" "<<a[u^s]<<' '<<b[u^s]<<endl;
                    f[u]=max(f[u],g[s]+b[u^s]);
                }
            }
            if(i==t.size()-1)ans=max(ans,f[u]);
      //      cout<<"  "<<u<<" "<<f[u]<<endl;
        }
    }
    printf("%d\n",ans);

}