#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];
set <pair <mi, mi>> f;
set <pii> candidate;
int Time = 0;

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

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

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

int dfs(mi &cura, mi &status) {
    if (cura.empty()) return 1;
    if (f.count(make_pair(cura, status))) return 0;
    f.insert(make_pair(cura, status));
    mi S = status;
    auto x = *cura.begin();
    for (auto [len, cnt] : S) {
        if (len > x.second) break;
        sub(status, len, 1);
        sub(cura, x.first, len);
        if (dfs(cura, status)) return 1;
        add(status, len, 1);
        add(cura, x.first, len);
    }
    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 (*max_element(c + 1, c + N + 1) > M) {
        puts("0"); return 0;
    }
    for (int i = 1, j; i <= M; i ++) {
        for (j = 1; j <= N && c[j] < i; j ++);
        if (j > N) break;
        for (int k; j <= N; j = k) {
            for (k = j; k <= N && c[k] >= i; k ++);
            a[++ t] = k - j;
            while (k <= N && c[k] < i) k ++;
        }
    }
    for (int i = 0; i < M; i ++) {
        scanf("%d%d", l + i, cost + i);
        b[i] = l[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));
        }
    }
    mi status;
    for (auto x : candidate) {
        status.clear();
        for (int i = 0; i < M; i ++) {
            if (x.second >> i & 1) add(status, l[i], 1);
        }
        // for (auto [len, cnt] : status) fprintf(stderr, "len = %d, cnt = %d\n", len, cnt);
        if (dfs(a, status)) {
            ans = -x.first; break;
        }
    }
    printf("%d\n", ans);
    return 0;
}