#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=double;
#define FOR(i,a,b) for(ll i=a;i<(ll)b;++i)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define aa first
#define bb second
#define PB push_back
#define EQ(a,b) (fabs(a-b)<=(fabs(a+b)*EPS))
#define MOD ((ll)(1e9+7))
#define MAXLISEK 22
#define MX (1ll << MAXLISEK)
#define INF (1ll << 40)
//#define DEBUG

ll n, l;
vector<int> boxes;
ll lisky[MAXLISEK]; // lengths of lisky
ll price[MAXLISEK]; // price of lisky

ll offset[MX];

ll length(ll mask) {
  ll res = 0;
  F(l) {
    ll bit = 1ll << i;
    res += lisky[i] * !!(bit & mask);
  }
  return res;
}

ll boxMem[MX]; // last unfilled box for a given mask
ll box(ll mask) {
  if (boxMem[mask] != -1) return boxMem[mask];
  ll ln = length(mask);
  F(boxes.size()) {
    if (ln < boxes[i]) return boxMem[mask] = i;
    ln -= boxes[i];
  }
  return boxes.size();
}


ll filledMem[MX]; // filled tiles in the last box completely unfilled for the given mask
ll filled(ll mask) {
  if (filledMem[mask] != -1) return filledMem[mask];
  ll ln = length(mask);
  F(boxes.size()) {
    if (ln < boxes[i]) return filledMem[mask] = ln;
    ln -= boxes[i];
  }
  return ln;
}

ll dp[MX];
ll rec(ll mask) {
  // remove each liska and check solution
  if (mask == 0) return 0;
  ll & d = dp[mask];
  if (d != -1) return d;
  d = -INF;
  for (int i = 0; i < l; ++ i) {
    ll bit = 1ll << i;
    const ll maskRem = mask & (~bit);
    if (maskRem == mask
        || box(maskRem) >= boxes.size()
        || lisky[i] + filled(maskRem) > boxes[box(maskRem)]) continue;
    d = max(d, rec(maskRem) + price[i]);
  }
  return d;
}

int main(){
  ios::sync_with_stdio(0);cin.tie(0);

  F(MX) dp[i] = filledMem[i] = boxMem[i] = -1;

  cin >> n >> l;
  vector<ll> hist(n);
  ll mx = 0;
  ll area = 0;
  F(n) {
    cin >> hist[i];
    mx = max(mx, hist[i]);
    area += hist[i];
  }
  ll curLen = 0;
  for (int i = 1; i <= mx; ++ i) {

    FF(n) {
      if (hist[j] < i) {
        if (curLen != 0) boxes.PB(curLen);
        curLen = 0;
      } else
        curLen ++;

      if (boxes.size() > l) {
        cout << 0 << endl;
        return 0;
      }
    }
    if (curLen) boxes.PB(curLen);
    curLen = 0;
  }

  // read the lisky
  F(l) {
    cin >> lisky[i] >> price[i];
  }

  // check all masks that have the length equal to the area of the histogram
  ll res = 0;
  F(MX) {
    if (length(i) == area) res = max(res, rec(i));
  }
#ifdef DEBUG
  cerr << "histogram: ";
  F(n) cerr << hist[i] << ' ';
  cerr << endl;

  cerr << "boxes: "; 
  F(boxes.size()) cerr << boxes[i] << ' ';
  cerr << endl;
  cerr << "LISKY: " << endl;
  F(l) {
    cout << lisky[i] << ' ';
  }
  cerr << endl;
  cerr << "DP: " << endl;
  F(16) {
    cerr << bitset<8>(i) << ": " << rec(i) << endl;
  }
  cerr << "LENGTH: " << endl;
  F(16) {
    cerr << bitset<8>(i) << ": " << length(i) << endl;
  }
  cerr << "BOX: " << endl;
  F(16) {
    cerr << bitset<8>(i) << ": " << box(i) << endl;
  }
  cerr << "FILLED: " << endl;
  F(16) {
    cerr << bitset<8>(i) << ": " << filled(i) << endl;
  }
#endif
  cout << res << endl;

  return 0;
}