#include <bits/stdc++.h>
using namespace std;

#define ST first
#define ND second
#define PB push_back

#define FAIL()         \
    {                  \
        cout << "0\n"; \
        return 0;      \
    }

int C[100000];
int T;
vector<int> XS;
pair<int, int> XT[20];

bool taken[16];
int value = 0;
int best = 0;

void rec(int s, int a) {
    for (int i = a; i < T; i++)
        if (!taken[i]) {
            if (XS[s] == XT[i].ST && s + 1 == (int)XS.size())
                best = max(value + XT[i].ND, best);
            else if (XS[s] >= XT[i].ST) {
                taken[i] = true;
                XS[s] -= XT[i].ST;
                value += XT[i].ND;

                if (XS[s])
                    rec(s, i + 1);
                else
                    rec(s + 1, 0);

                taken[i] = false;
                XS[s] += XT[i].ST;
                value -= XT[i].ND;
            }
        }
}

int main() {
    ios_base::sync_with_stdio(0);

    int H;
    cin >> H >> T;

    for (int i = 0; i < H; i++) {
        cin >> C[i];
        if (C[i] > T) FAIL();
    }

    for (int i = 0; i < T; i++) cin >> XT[i].ST >> XT[i].ND;

    for (int c = 1; c <= T; c++)
        for (int i = 0; i < H; i++)
            if (C[i] >= c) {
                int j = 1;
                while (j < H && C[i + j] >= c) j++;
                i += j;
                XS.PB(j);
                if ((int)XS.size() > T) FAIL();
            }

    if (XS.size() == 0) FAIL();

    sort(XS.begin(), XS.end());
    sort(XT, XT + T);

    rec(0, 0);
    cout << best << '\n';
}