#include<bits/stdc++.h>

using namespace std;

vector<int> len;

int h, n;

int input[100001];

void init(){
    cin >> h >> n;
    for(int i=0;i<h;i++){
        cin >> input[i];
    }
    input[h]=0;
    for(int i=1;i<=16;i++){
        int start=0;
        for(int j=0;j<=h;j++){
            if(input[j] < i){
                if(start<j){
                    len.push_back(j-start);
                }
                start=j+1;
            }
        }
    }
}

vector<pair<int,int>> teams;

int main(){
    init();
    for(int i : len){
        //cout << i << '\n';
    }
    sort(len.begin(), len.end());
    teams.resize(n);
    vector<int> perm(n);
    for(int i=0;i<n;i++){
        cin >> teams[i].first >> teams[i].second;
        perm[i] = i;
    }
    int maxi = 0;
    do{
        multiset<int> ms;
        for(int i=0;i<n && i<len.size();i++){
            ms.insert(len[i]);
        }
        int result = 0;
        vector<int> in;
        for(int i=0;i<n;i++){
            auto it = ms.lower_bound(teams[perm[i]].first);
            if(it != ms.end()){
                int m = *it;
                ms.erase(it);
                ms.insert(m-teams[perm[i]].first);
                result+=teams[perm[i]].second;
                in.push_back(perm[i]);
            }
        }
        bool ok = 1;
        for(int i : ms){
            if(i!=0){
                ok=0;
            }
        }
        if(maxi < result && ok){
            maxi = result;
        }
    } while(next_permutation(perm.begin(), perm.end()));
    cout << maxi << '\n';
return 0;
}