#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int a[100005],l[20],c[20],val[1<<16],sum[1<<16],f[1<<16],g[1<<16];
int n,m;
int main(){
    // freopen("h.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    for (int h=1;h<=m;++h){
        int t=0;
        for (int i=1;i<=n;++i)
            if (a[i]>=h) ++t;
            else{
                q.emplace(t);
                if (q.size()>m) q.pop();
                t=0;
            }
        if (t){
            q.emplace(t);
            if (q.size()>m) q.pop();
            t=0;
        }
    }
    for (int i=1;i<=m;++i) scanf("%d%d",&l[i],&c[i]);
    for (int s=0;s<(1<<m);++s){
        for (int i=1;i<=m;++i)
            if (s&(1<<i-1)) sum[s]+=l[i],val[s]+=c[i];
    }
    for (int s=0;s<(1<<m);++s) f[s]=-1e8;
    f[0]=0;
    while (!q.empty()){
        int L=q.top();q.pop();
        for (int s=0;s<(1<<m);++s) g[s]=f[s];
        for (int s=0;s<(1<<m);++s)
            if (f[s]>=0){
                int T=((1<<m)-1)^s;
                for (int t=T;t;t=(t-1)&T)
                    if (sum[t]<=L)
                        g[s|t]=max(g[s|t],f[s]+val[t]);
            }
        for (int s=0;s<(1<<m);++s) f[s]=g[s];
    }
    int ans=0;
    for (int s=0;s<(1<<m);++s) ans=max(ans,f[s]);
    printf("%d\n",ans);
    return 0;
}