#include <bits/stdc++.h>

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()
#define fout(x) {cout << x << "\n"; return; }

using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 1123456;
const int M = pw(16);
const ll inf = 1e18;
const long long mod = 1e9 + 7;
const long long N = 3e5;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

bool dp[17][M];
ll sum[M];
int b[N];

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, t;

    cin >> n >> t;

    int N = 0;

    vector <int> a(n + 1);

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        N = max(a[i], N);
    }

    if(N == 0){
        cout << "0\n";
        return 0;
    }

    vector <ll> _t(t), cost(t);

    for(int i = 0; i < t; i++){
        cin >> _t[i] >> cost[i];
    }

    vector <ll> va;

    for(int step = 1; step <= N; step++){
        int l = 0;
        for(int i = 1; i <= n; i++){
            b[i] = 0;
            if(a[i] >= step){
                b[i] = 1;
            }
            if(!b[i]){
                if(l){
                    va.p_b(l);
                }
                l = 0;
            }else{
                l++;
            }
        }
        if(l){
            va.p_b(l);
        }
    }

    sort(all(va));

    if(sz(va) > t){
        cout << "0\n";
        return 0;
    }

    dp[0][0] = 1;

    for(int i = 0; i < pw(t); i++){
        for(int j = 0; j < t; j++){
            if((i & pw(j))){
                sum[i] += _t[j];
            }
        }
    }
    
    int musk;

    for(int i = 1; i <= sz(va); i++){
        for(int j = 0; j < pw(t); j++)if(dp[i - 1][j]){
            for(int i1 = j; i1 < pw(t); i1 = (i1 + 1) | j){
                musk = i1 ^ j;
                if(sum[musk] == va[i - 1]){
                    dp[i][i1] = 1;
                }
            }
        }
    }

    ll ans = 0;

    for(int i = 0; i < pw(t); i++)if(dp[sz(va)][i]){
        ll s = 0;
        for(int j = 0; j < t; j++){
            if((i & pw(j))){
                s += cost[j];
            }
        }
        ans = max(ans, s);
    }

    cout << ans << "\n";

    return 0;
}