#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>

#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#pragma GCC target("avx2")

#define deb(x) cout << #x << " = " << x << "\n"
#define all(x) (x).begin(), (x).end()
#define len(x) (int) x.size()
#define lsb(x) (x) & -(x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define v(x) (int)(x - 'a')

#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ld, ld> pld;
typedef pair <ll, ll> pll;

template <class T1, class T2 = less <T1>> using pb_heap = __gnu_pbds::priority_queue <T1, T2, binary_heap_tag>;
template <class T1, class T2 = null_type, class T3 = less <T1>> using pb_map = tree <T1, T2, T3, rb_tree_tag, tree_order_statistics_node_update>;
template <class T1, class T2 = null_type, class T3 = hash <T1>> using pb_umap = gp_hash_table <T1, T2, T3>;
template <class T1, class T2, class T3 = hash <T1>> using umap = unordered_map <T1, T2, T3>;
template <class T> using uset = unordered_set <T>;
template <class T> using vec = vector <T>;

const ll infll = numeric_limits <ll>::max() >> 1;
const int inf = numeric_limits <int>::max() >> 1;
const int N = 1e5 + 1;
const int T = 16;
int h, t, height[N], leng[T], cost[T], sumc[1 << T], suml[1 << T], dp[T][1 << T];

vec <int> intervals;

void input() {
    cin >> h >> t;
    for (int i = 1; i <= h; ++i) {
        cin >> height[i];
    }
    for (int i = 0; i < t; ++i) {
        cin >> leng[i] >> cost[i];
        sumc[1 << i] = cost[i];
        suml[1 << i] = leng[i];
    }
    for (int j = 0; j < T; ++j) {
        for (int i = 0; i < (1 << T); ++i) {
            if ((i >> j) & 1) {
                sumc[i] += sumc[i ^ (1 << j)];
                suml[i] += suml[i ^ (1 << j)];
            }
        }
    }
}

void solve() {
    if (*max_element(height + 1, height + h + 1) > t) {
        cout << "0\n";
        return;
    }
    for (int i = 1; i <= t; ++i) {
        int left = -1;
        for (int j = 1; j <= h; ++j) {
            if (height[j] >= i) {
                if (left == -1) {
                    left = j;
                }
            } else {
                if (left != -1) {
                    intervals.pb(j - left);
                }
                left = -1;
            }
        }
        if (left != -1) {
            intervals.pb(h + 1 - left);
        }
    }
    if (len(intervals) > t) {
        cout << "0\n";
        return;
    }
    fill(dp[0], dp[T], -inf);
    for (int i = 0; i < len(intervals); ++i) {
        for (int mask = 0; mask < (1 << t); ++mask) {
            for (int submask = mask; submask; submask = (submask - 1) & mask) {
                if (suml[submask] == intervals[i]) {
                    dp[i][mask] = max(dp[i][mask], sumc[submask] + (i? dp[i - 1][mask ^ submask]: 0));
                }
            }
        }
    }
    int res = 0;
    for (int mask = 0; mask < (1 << t); ++mask) {
        res = max(res, dp[len(intervals) - 1][mask]);
    }
    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    input();
    solve();
}

/*
3 4
2 1 2
3 2
1 1
1 2
1 3

4 7
2 2 1 1
3 1
1 1
1 4
1 1
2 4
2 2
2 1

10 16
1 1 1 1 1 1 1 1 1 1
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
*/