#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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 + 2);

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

        if (x <= k) {
            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; ++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; });

    vector<int> weight(1 << k);
    vector<int> income(1 << k);
    vector<bool> dp(1 << k, false);
    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] = true;
        }

        //cout << "k = 0, mask = " << mask << " | " << dp[mask] << "\n";
    }

    for (int i = 1; i < k; ++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] <= segments[i]) {
                    dp[mask] = dp[smask];
                }
            }
            //cout << "k = " << i << ", mask = " << mask << " | " << dp[mask] << "\n";
        }
    }

    /*
    for (int i = 0; i < k; ++i) {
        cout << segments[i] << " ";
    }
    cout << "\n";
    */

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

    cout << res << "\n";
}