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

using namespace std;

constexpr int max_teams = 16, inf = 1e9;

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

    for (int i = 0; i < (1 << k); ++i) {
        dp[i] = -inf;
    }

    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]) {
                if (i - last - 1 > 0)
                    segments.push_back(i - last - 1);
                last = i;
            }
        }
    }

    if (segments.size() > k) {
        cout << 0 << '\n';
        return 0;
    }

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

    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] = 1;
        }
    }

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

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

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