#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<=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;
        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;
            }
            map<pair<int,int>, int> m;
            m[{0,0}] = 0;
            do{
                int currInd=0, currD=0, nyer=0;
                for(int i=0;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;
                        }
                        m[{currInd, currD}]=max(m[{currInd, currD}], nyer);
                    } else {
                        break;
                    }
                }
            } while(next_permutation(perm.begin(), perm.end()));

            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(m.count({currInd, currD})){
                    maxi = max(maxi, nyer+m[{currInd, currD}]);
                }
                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(m.count({currInd, currD})){
                            maxi = max(maxi, nyer+m[{currInd, currD}]);
                        }
                    } else {
                        break;
                    }
                }
            } while(next_permutation(perm.begin(), perm.end()));

        }
    }
    cout << maxi << '\n';
return 0;
}