#include <bits/stdc++.h>

using namespace std;
const int c=16, c2=1<<c;
int h, n, n2, t[100005];
int hossz[c2], sum[c2];
bool rossz[c2], regi[c2], uj[c2];
vector<int> len, ert;
vector<pair<int, int> > sz;
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> h >> n;
    n2=(1<<n);
    for (int i=1; i<=h; i++) {
        cin >> t[i];
        if (t[i]>n) {
            cout << 0 << "\n";
            return 0;
        }
    }
    for (int i=1; i<=h+1; i++) {
        if (t[i]>=t[i-1]) {
            for (int j=1; j<=t[i]-t[i-1]; j++) {
                ert.push_back(i);
            }
        } else {
            for (int j=1; j<=t[i-1]-t[i]; j++) {
                len.push_back(i-ert.back());
                ert.pop_back();
            }
        }
    }
    if (len.size()>n) {
        cout << 0 << "\n";
        return 0;
    }
    for (int i=0; i<n; i++) {
        int x, y;
        cin >> x >> y;
        sz.push_back({x, y});
    }
    sort(sz.begin(), sz.end());
    for (int i=0; i<n2; i++) {
        for (int j=0; j<n; j++) {
            if (i & (1<<j)) {
                hossz[i]+=sz[j].first;
                sum[i]+=sz[j].second;
            }
        }
        for (int j=0; j<n-1; j++) {
            if ((i & (1<<j)) && ((i & (1<<(j+1)))==0) && sz[j].first==sz[j+1].first) {
                rossz[i]=1;
            }
        }
        //cout << "mask " << i << " " << hossz[i] << " " << sum[i] << " " << rossz[i] << "\n";
    }

    regi[0]=1;
    for (auto x:len) {
        vector<int> s;
        for (int i=0; i<n2; i++) {
            if (hossz[i]==x) {
                s.push_back(i);
            }
        }
        for (int i=0; i<n2; i++) {
            if (regi[i]) {
                for (auto y:s) {
                    if ((i & y) == 0) {
                        uj[i+y]=1;
                    }
                }
            }
        }
        for (int i=0; i<n2; i++) {
            regi[i]=(uj[i] && !rossz[i]);
            uj[i]=0;
        }
    }
    int ans=0;
    for (int i=0; i<n2; i++) {
        if (regi[i]) {
            ans=max(ans, sum[i]);
        }
    }
    cout << ans << "\n";
    return 0;
}

/*
3 1
1 1 1
3 1


*/