#include <bits/stdc++.h>

using namespace std;

constexpr int max_teams = 16;

int weight[1 << max_teams];
int income[1 << max_teams];
int dp[1 << max_teams];

struct Team {
    int days;
    int income;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<vector<int>> store_patrols(k + 3);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        if (x <= k + 1) {
            store_patrols[x + 1].push_back(i + 1);
        }
    }

    vector<Team> teams(k);
    for (int i = 0; i < k; ++i) {
        cin >> teams[i].days >> teams[i].income;
    }

    vector<int> segments;
    vector<bool> blocked(n + 2);
    blocked[0] = true;
    blocked[n + 1] = true;
    for (int store = 1; store <= k + 1; ++store) {
        for (int x : store_patrols[store]) {
            blocked[x] = true;
        }

        int last = 0;
        for (int i = 1; i < (int) blocked.size(); ++i) {
            if (blocked[i]) {
                segments.push_back(i - last - 1);
                last = i;
            }
        }
    }

    sort(segments.begin(), segments.end(), [](int x, int y) { return x > y; });
    dp[0] = true;

    for (int mask = 1; mask < (1 << k); ++mask) {
        for (int i = 0; i < k; ++i) {
            if (mask & (1 << i)) {
                weight[mask] = weight[mask ^ (1 << i)] + teams[i].days;
                income[mask] = income[mask ^ (1 << i)] + teams[i].income;
                break;
            }
        }

        if (weight[mask] <= segments[0]) {
            dp[mask] = weight[mask];
        }
    }

    
    for (int i = 1; i < k; ++i) {
        int segment = segments[i];
        for (int mask = (1 << k) - 1; mask; --mask) {
            for (int smask = mask; smask; smask = (smask - 1) & mask) {
                int xmask = mask ^ smask;
                if (weight[xmask] <= segment and dp[smask]) {
                    dp[mask] = max(dp[mask], dp[smask] + weight[xmask]);

                    break;
                }
            }
        }
    }

    int res = 0;
    for (int mask = 1; mask < (1 << k); ++mask) {
        if (dp[mask]) {
            res = max(res, income[mask]);
        }
    }

    if (*max_element(dp, dp + (1 << k)) < accumulate(segments.begin(), segments.end(), 0)) {
        cout << 0 << "\n";
    } else {
        cout << res << "\n";
    }
}