#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef map <int, int> mi;

const int MAX_N = 100000 + 5;
const int INF32 = 0x3f3f3f3f;
const int lim = 5000000;

int N, M, c[MAX_N], l[MAX_N], cost[MAX_N], b[MAX_N], t;
mi a;
int totlen[MAX_N], totcost[MAX_N];
map <pair <mi, mi>, int> f;
set <pii> candidate;
int Time = 0;

void add(mi &a, int pos) {
    if (a.count(pos)) {
        if (!++ a[pos]) a.erase(pos);
    }else a[pos] = 1;
}

void sub(mi &a, int pos) {
    if (a.count(pos)) {
        if (!-- a[pos]) {
            a.erase(pos);
        }
    }else {
        a[pos] = -1;
    }
}

void debug(mi &x) {
    for (auto [pos, cnt] : x) fprintf(stderr, "pos = %d, cnt = %d\n", pos, cnt);
}

int dfs(mi &cura, mi &status, int tot) {
    // debug(cura);
    // fprintf(stderr, "status = %d\n", status);
    if (cura.empty()) return 1;
    pair <mi, mi> tmp = make_pair(cura, status);
    if (f.count(tmp)) return f[tmp];
    f[tmp] = 0;
    // int sum = 0;
    // for (auto [pos, cnt] : cura) {
    //     if (cnt > 0) {
    //         sum += cnt;
    //         if (sum > tot) break;
    //     }
    // }
    // if (sum > tot) return 0;
    auto x = *cura.begin();
    if (x.second < 0) return 0;
    else {
        sub(cura, x.first);
        // cura.erase(cura.begin());
        // if (-- x.second) cura.insert(x);
    }
    mi S = status;
    for (auto [len, cnt] : S) {
        if (x.first + len > N + 1) break;
        sub(status, len);
        add(cura, x.first + len);
        if (dfs(cura, status, tot - 1)) return f[tmp] = 1;
        add(status, len);
        sub(cura, x.first + len);
    }
    add(cura, x.first);
    return 0;
}

int main() {
    scanf("%d%d", &N, &M);
    ll sumC = 0;
    for (int i = 1; i <= N; i ++) {
        scanf("%d", c + i);
        sumC += c[i];
        if (c[i] != c[i - 1]) a[i] = c[i] - c[i - 1];
    }
    if (c[N]) a[N + 1] = -c[N];
    for (int i = 0; i < M; i ++) {
        scanf("%d%d", l + i, cost + i);
        b[i] = l[i];
    }
    sort(b, b + M);
    t = unique(b, b + M) - b;
    int ans = 0;
    for (int s = 1; s < (1 << M); s ++) {
        int ctz = __builtin_ctz(s);
        totlen[s] = totlen[s ^ (1 << ctz)] + l[ctz];
        totcost[s] = totcost[s ^ (1 << ctz)] + cost[ctz];
        if (sumC == totlen[s]) {
            candidate.insert(make_pair(-totcost[s], s));
        }
    }
    for (int i = 0; i < M; i ++) l[i] = lower_bound(b, b + t, l[i]) - b;
    mi status;
    for (auto x : candidate) {
        status.clear();
        for (int i = 0; i < M; i ++) {
            if (x.second >> i & 1) add(status, b[l[i]]);
        }
        if (dfs(a, status, __builtin_popcount(x.second))) {
            ans = -x.first; break;
        }
    }
    printf("%d\n", ans);
    return 0;
}