#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double ld;
typedef vector<ll> vi;
// push_back insert lower_bound upper_bound erase 

struct Liska{
    ll length, score;
};

struct S{
    ll score, idx, val;
};

int main(int argc, char **argv){
    ll C, L;
    cin >> C >> L;
    vector<ll> columns(C);for(ll &n:columns)cin>>n;
    columns.push_back(0);
    vi rows, stack;
    ll last = 0;
    for(ll i=0; i<=C; ++i){
        ll current = columns[i];
        for(ll j=last; j<current; ++j){
            stack.push_back(i);
            /* cerr<<"stack push "<<i<<endl; */
            if(stack.size() > L){
                cout << 0 << endl; exit(0);
            }
        }
        for(ll j=current; j<last; ++j){
            ll val = stack.back(); stack.pop_back();
            /* cerr<<"stack pop "<<val<<' ' <<i<<endl; */
            ll dif = i-val;
            rows.push_back(dif);
        }
        last=current;
    }
    ll R=rows.size();
    /* cerr<<"rows: ";for(ll n:rows)cerr<<n<<' ';cerr<<endl; */
    vector<Liska> lisky(L);for(Liska &l:lisky)cin>>l.length>>l.score;
    sort(rows.rbegin(),rows.rend());
    vector<S> dp(1<<L, {-1,0,0});
    dp[0]={0,0,0};
    ll best_score = 0;
    for(ll s=1; s<dp.size(); ++s){
        S best = {-1,0,0};
        for(ll bit=0; bit<L; ++bit){
            ll b=(1<<bit);
            if(s & b){
                ll subs = s ^ b;
                S substate = dp[subs];
                if(substate.idx == R) continue; // skip if child already won
                substate.val += lisky[bit].length;
                substate.score += lisky[bit].score;
                /* cerr << substate.val << ' ' << rows[substate.idx] << endl; */
                if(substate.val > rows[substate.idx]){
                    substate = {-1,0,0};
                }else if(substate.val==rows[substate.idx]){
                    ++substate.idx;
                    substate.val = 0;
                    if(substate.idx == R){
                        best_score = max(best_score, substate.score);
                        /* cerr << "new best score " << best_score << endl; */
                    }
                }
                if(best.score < substate.score) best = substate;
            }
        }
        dp[s] = best;
        /* cerr << "best for "<<(bitset<10>(s))<<" is "<<best.score << endl; */
    }
    cout << best_score << endl;
    return 0;
}