#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

#define S 100007

using namespace std;

int T[S];
int K[S];
int C[S];

vector < int > V;
vector < int > V2;

priority_queue < int > q;

int main(void){
    int n,t;
    scanf("%d %d",&n,&t);
    for(int i = 1; i <= n;i++){
        scanf("%d",&T[i]);
    }
    for(int i = 1; i <= t;i++){
        scanf("%d %d",&K[i],&C[i]);
    }
    for(int h = 1; h <= 16;h++){
        int dl = 0;
        for(int i = 1; i <= n+1;i++){
            if(T[i] >= h){
                dl++;
            }else{
                if(dl){
                    V.push_back(dl);
                    dl = 0;
                }else{

                }
            }
        }
    }
    if(V.empty()){
        printf("0");
        return 0;
    }
    sort(V.begin(),V.end());
    reverse(V.begin(),V.end());
    while(V.size() > 16)
        V.pop_back();
    int odp = 0;
    for(int i = 1; i < (1 << t);i++){
        int p = 1;
        V2.clear();
        for(int j = 1; j <= t;j++){
            if(i & p){
                V2.push_back(K[j]);
            }
            p *= 2;
        }
        while(!q.empty())
            q.pop();
        for(int j = 0; j < V.size();j++){
            q.push(V[j]);
        }
        bool blad = false;
        sort(V2.begin(),V2.end());
        for(int j = V2.size()-1; j >= 0;j--){
            if(q.top() < V2[j]){
                blad = true;
            }else{
                q.push(q.top() - V2[j]);
                q.pop();
            }
        }
        if(!blad){
            int pom = 0;
            p = 1;
            for(int j = 1; j <= t;j++){
                if(i & p){
                    pom += C[j];
                }
                p *= 2;
            }
            odp = max(odp,pom);
        }
    }
    printf("%d",odp);
    return 0;
}