#include<bits/stdc++.h>

using namespace std;

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};

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<=20;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();
    if(len.size() > n){
        cout << 0 << '\n';
        return 0;
    }
    sort(len.begin(), len.end());
    /*for(int i : len){
        cout << i << ' ';
    }
    cout<< "\n\n";*/
    teams.resize(n);
    for(int i=0;i<n;i++){
        cin >> teams[i].first >> teams[i].second;
    }
    int maxi = 0;
    for(int i = 0;i< (1<<n);i++){
        vector<pair<int,int>> team1;
        vector<pair<int,int>> team2;
        for(int j=0;j< n;j++){
            if(i & (1<<j)){
                team1.push_back(teams[j]);
            } else {
                team2.push_back(teams[j]);
            }
        }
        if(team1.size() == n/2){
            /*cout << "team1 ";
            for(auto& a : team1){
                cout << a.first << ' ' << a.second << ';';
            }
            cout << "team2 ";
            for(auto& a : team2){
                cout << a.first << ' ' << a.second << ';';
            }
            cout << '\n';*/
            vector<int> perm(team1.size());
            for(int i=0;i<team1.size();i++){
                perm[i] = i;
            }
            unordered_map<pair<int,int>, int, hash_pair> m;
            m[{0,0}] = 0;
            bool oksi = 0;
            int tcurrInd, tcurrD, ertek;
            do{
                int currInd=0, currD=0, nyer=0;
                int i=0;
                for(;i<team1.size() && currInd<len.size();i++){
                    if(team1[perm[i]].first+currD <= len[currInd]){
                        nyer+=team1[perm[i]].second;
                        currD+=team1[perm[i]].first;
                        if(currD == len[currInd]){
                            currD = 0;
                            ++currInd;
                        }
                        if(currInd == len.size()){
                            maxi = max(maxi, nyer);
                        }
                        //m[{currInd, currD}]=max(m[{currInd, currD}], nyer);
                    } else {
                        break;
                    }
                }
                if(i == team1.size()){
                    oksi = 1;
                    tcurrInd=currInd;
                    tcurrD=currD;
                    ertek = nyer;
                }
            } while(next_permutation(perm.begin(), perm.end()));
            if(oksi){
                perm.resize(team2.size());
                for(int i=0;i<team2.size();i++){
                    perm[i] = i;
                }
                do{
                    int currInd=len.size(), currD=0, nyer=0;
                    if(currInd == tcurrInd && currD == tcurrD){
                        maxi = max(maxi, nyer+ertek);
                    }
                    for(int i=0;i<team2.size() && currInd >=0;i++){
                        if(currD == 0){
                            --currInd;
                            if(currInd >=0)
                                currD = len[currInd];
                        }
                        if(currInd >=0 && currD-team2[perm[i]].first >= 0){
                            nyer+=team2[perm[i]].second;
                            currD-=team2[perm[i]].first;
                            if(currInd == tcurrInd && currD == tcurrD){
                                maxi = max(maxi, nyer+ertek);
                            }
                        } else {
                            break;
                        }
                    }
                } while(next_permutation(perm.begin(), perm.end()));
            }
        }
    }
    cout << maxi << '\n';
return 0;
}