#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ll long long

using namespace std;

const int MAXN = 200100;
int arr[MAXN];
int D[MAXN], V[MAXN];
vector <int> ve;

int val[MAXN], dulj[MAXN];
int dp[MAXN];

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

    int n, t;
    cin >> n >> t;

    REP(i, n) cin >> arr[i];
    REP(i, t) cin >> D[i] >> V[i];

    REP(k, t) {
        int tr = 0;
        REP(i, n) {
            if (arr[i] == 0) {
                ve.push_back(tr);
                tr = 0;
            } else {
                tr++;
                arr[i]--;
            }
        }
        if (tr) ve.push_back(tr);
    }

    sort(ve.begin(), ve.end());
    reverse(ve.begin(), ve.end());
    ve.resize(t);
    reverse(ve.begin(), ve.end());

    REP(mask, (1 << t)) {
        REP(i, t) {
            if (mask & (1 << i)) {
                val[mask] += V[i];
                dulj[mask] += D[i];
            }
        }
    }

    int all = (1 << t) - 1;

    dp[0] = 1;
    for (int d : ve) {
        for (int mask = (1 << t) - 1; mask >= 0; mask--) {
            if (dp[mask] == 1) continue;

            for (int x = mask; x > 0; x = (x - 1) & mask) {
                if (dp[mask ^ x] == 0) continue;

                if (dulj[x] <= d) {
                    dp[mask] = 1;
                    break;
                }
            }
        }
    }

    int out = 0;
    REP(i, (1 << t)) {
        if (dp[i]) out = max(out, val[i]);
    }
    cout << out << "\n";



    return 0;
}