#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin>>n>>k;

    vector<int> h(n);
    for(int &x : h)
        cin>>x;

    vector<int> v(k), vc(k);
    for(int i = 0; i < k; i++)
        cin>>v[i]>>vc[i];

    int maxE = *max_element(h.begin(), h.end());
    if(maxE > k){
        cout<<"0\n";
        return 0;
    }

    vector<vector<bool>> dpb;
    for(int i = 1; i <= maxE; i++){
        vector<int> ints;
        int last = -2;
        for(int j = 0; j < n; j++){
            if(h[j] < i) continue;
            if(last+1 < j)
                ints.push_back(1);
            else
                ints.back()++;
            last = j;
        }

        /*cout<<"ints: ";
        for(auto p : ints)
            cout<<p<<" ";
        cout<<'\n';*/

        vector<pair<int, int>> dp(1<<k);
        for(int j = 1; j < (1<<k); j++)
            dp[j].first = -1;
        dp[0] = make_pair(0, ints[0]);
        for(int j = 1; j < (1<<k); j++){
            for(int l = 0; l < k; l++){
                if((j&(1<<l)) == 0) continue;
                int x = j^(1<<l);
                if(dp[x].first == -1 || dp[x].first == (int)ints.size()) continue;
                if(dp[x].second > v[l])
                    dp[j] = make_pair(dp[x].first, dp[x].second - v[l]);
                else if (dp[x].second == v[l])
                    dp[j] = make_pair(dp[x].first+1, dp[x].first+1 < (int)ints.size() ? ints[dp[x].first+1] : 0);
            }
        }
        dpb.push_back(vector<bool>(1<<k, false));
        for(int j = 0; j < (1<<k); j++){
            //cout<<j<<": ";
            if(dp[j].first == (int)ints.size())
                dpb.back()[j] = true;
        }
    }

    if(dpb.size() == 0){
        cout<<"0\n";
        return 0;
    }

    vector<bool> meg = dpb[0];
    for(int i = 1; i < maxE; i++){
        vector<bool> temp(1<<k, false);
        for(int j = 0; j < (1<<k); j++){
            if(!dpb[i][j]) continue;
            int x = ((1<<k)-1)^j;
            bool jo = false;
            for(int l = x; l > 0; l = ((l-1)&x))
                temp[j|l] = temp[j|l] || meg[l];
        }
        swap(temp, meg);
    }

    int ki = 0;
    for(int i = 0; i < 1<<k; i++){
        if(!meg[i]) continue;
        int ossz = 0;
        for(int j = 0; j < k; j++)
            if(i&(1<<j))
                ossz += vc[j];
        ki = max(ki, ossz);
    }

    cout<<ki<<'\n';

    return 0;
}