#include <iomanip>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;


vector<int> chlievik;

struct team{
    int d;
    int i;

    bool operator<(team &b){
        return this->d < b.d;
    }
};

vector<team> teams;
vector<int> choices;
vector<int> chyba;
int dokopychyba;
int h,t;

int bruteforce(int chosen){
    // cout<<'d'<<dokopychyba<<'\n';
    if (dokopychyba == 0){
        int sum=0;
        for(int i=0;i<t;i++){
            if (choices[i]!=-1){
                sum += teams[i].i;
            }
        }
        return sum;
    }
    if(chosen == t)return 0;

    int D = teams[t-chosen-1].d;

    int best = 0;
    for(int i=0;i<chlievik.size();i++){
        if(D<=chyba[i]){
            choices[t-chosen-1] = i;
            dokopychyba -= D;
            chyba[i]-=D;
            int res = bruteforce(chosen+1);
            if (res>best)best=res;
            chyba[i]+=D;
            dokopychyba += D;
            choices[t-chosen-1] = -1;
        }
    }
    int res = bruteforce(chosen+1);
    if (res>best)best=res;

    return best;
}


int main(){
    cin>>h>>t;
    vector<int> c(h+1,0);
    int sumc = 0;
    int sumd = 0;
    for(int i=0;i<h;i++){
        cin>>c[i];
        sumc += c[i];
        if (c[i]>t){
            cout<<"0\n";
            return 0;
        }
    }

    teams = vector<team>(t);

    for(int i=0;i<t;i++){
        cin>>teams[i].d>>teams[i].i;
        sumd += teams[i].d;
    }
    dokopychyba = sumc;
    if (sumc>sumd){
        cout<<"0\n";
        return 0;
    }

    vector<int> stack;
    int prev = 0;
    for(int i=0; i<h+1; i++){
        if (c[i]>prev){
            for(int j=0;j<c[i]-prev;j++){
                stack.push_back(i);
            }
        } else {
            for(int j=0;j<prev-c[i];j++){
                chlievik.push_back(i-stack.back());
                stack.pop_back();
            }
        }
        prev = c[i];
    }

    sort(chlievik.begin(),chlievik.end());
    chyba = chlievik;
    sort(teams.begin(),teams.end());

    int chosen =0;
    choices = vector<int>(t,-1);
    int res = bruteforce(chosen);

    cout<<res<<'\n';
}