#include <bits/stdc++.h>

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

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

int N, M, c[MAX_N], l[MAX_N], cost[MAX_N];
mi a;
int totlen[MAX_N], totcost[MAX_N];
map <pair <mi, int>, int> f;
set <pair <int, int>> 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, int status, int tot) {
    // debug(cura);
    // fprintf(stderr, "status = %d\n", status);
    Time ++;
    if (Time > lim) {
        printf("0\n");
        exit(0);
    }
    if (cura.empty()) return 1;
    pair <mi, int> 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);
    }
    int S = status;
    while (S) {
        int ctz = __builtin_ctz(S);
        if (x.first + l[ctz] <= N + 1) {
            add(cura, x.first + l[ctz]);
            if (dfs(cura, status ^ 1 << ctz, tot - 1)) return f[tmp] = 1;
            sub(cura, x.first + l[ctz]);
        }
        S ^= (1 << ctz);
    }
    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);
    }
    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 (auto x : candidate) {
        if (dfs(a, x.second, __builtin_popcount(x.second))) {
            ans = -x.first; break;
        }
    }
    printf("%d\n", ans);
    return 0;
}