#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <cstring>
#include <vector>
#include <bitset>
#include <set>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1e5, K = 16;

int cnt[N + 5], d[(1 << K) + 5], v[(1 << K) + 5], dp[(1 << K) + 5];

struct Array {
    int h, id;
    bool operator < (const Array &s) const {
        return h < s.h;
    }
};
Array a[N + 5];

int main() {
    int n, m;
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(a[i].h);
        a[i].id = i;
    }
    std::sort(a + 1, a + n + 1);
    std::set<int> S;
    S.insert(n + 1);
    int now = 1;
    for (int i = 1; i <= 16; ++i) {
        while (now <= n && a[now].h < i) S.insert(a[now].id), ++now;
        int pos = 0;
        for (auto x : S) {
            if (x > pos + 1) ++cnt[x - pos - 1];
            pos = x;
        }
    }
    std::vector<int> Vec;
    now = N;
    for (int i = 1; i <= m; ++i) {
        while (!cnt[now] && now) --now;
        if (!now) break;
        --cnt[now];
        Vec.push_back(now);
    }

    int M = 1 << m;
    for (int i = 1; i <= m; ++i) {
        int dd, vv;
        read(dd), read(vv);
        for (int j = 0; j < M; ++j)
            if (j & (1 << (i - 1))) d[j] += dd, v[j] += vv;
    }
    dp[M - 1] = 0;
    for (int x : Vec) {
        for (int i = 0; i < M; ++i)
            for (int j = i; j; j = i & (j - 1)) {
                if (d[j] <= x) dp[i ^ j] = std::max(dp[i ^ j], dp[i] + v[j]);
            }
    }

    int ans = 0;
    for (int i = 0; i < M; ++i) ans = std::max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}