#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

#define f first
#define s second

const int INF = 1e9, H = 1e5 + 10, T = 16;
int h, t, arr[H];

pii seg[4 * H];

pii query(int i, int l, int r, int ql, int qr) {
  if (l >= ql && r <= qr) return seg[i];
  if (l > qr || r < ql) return {INF, h};
  int m = (l + r + 1) / 2;
  return min(query(i * 2, l, m - 1, ql, qr),
             query(i * 2 + 1, m, r, ql, qr));
}

pii update(int i, int l, int r, int ux, pii uv) {
  if (l >= ux && r <= ux) return seg[i] = uv;
  if (l > ux || r < ux) return seg[i];
  int m = (l + r + 1) / 2;
  return seg[i] = min(update(i * 2, l, m - 1, ux, uv),
                      update(i * 2 + 1, m, r, ux, uv));
}

map<int, long long> cnt;

void rek(int l, int r, int ph) {
  if (l > r)
    return;
  auto p = query(1, 0, h, l, r);
  if (p.first - ph > 0)
    cnt[r - l + 1] += p.first - ph;
  rek(l, p.second - 1, p.first);
  rek(p.second + 1, r, p.first);
}

pll dp[1 << T];
vector<pll> v;
int w[T], val[T], ans;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> h >> t;

  fill(seg, seg + H * 4, make_pair(INF, h));

  for (int i = 0; i < h; i++) {
    cin >> arr[i];
    update(1, 0, h, i, {arr[i], i});
  }

  for (int i = 0; i < t; i++)
    cin >> w[i] >> val[i];

  rek(0, h - 1, 0);

  int sum = 0;
  for (auto it = cnt.rbegin(); it != cnt.rend(); it++) {
    sum += it->second;
    v.push_back({sum - 1, it->first});
  }
  v.push_back({ll(1e18), 0});

//  for (auto p : v) {
//    cout << p.f << "," << p.s << " ";
//  }
//  cout << endl;

  dp[0] = {0ll, 0ll};
  for (int i = 1; i < (1 << t); i++) {
    dp[i] = {ll(1e18), h};
    sum = 0;

    for (int j = 0; j < t; j++) {
      if (i & (1 << j)) {
        sum += val[j];

        auto p = dp[i - (1 << j)];
        if (p.f < ll(1e18)) {
          int k1 = lower_bound(v.begin(), v.end(), make_pair(p.f, 0ll))->s;
          int k2 = lower_bound(v.begin(), v.end(), make_pair(p.f + 1, 0ll))->s;
//          cout << "mask " << i << " tries from mask " << (i - (1 << j)) << endl;
//          cout << "p is " << p.f << " " << p.s << endl;
//          cout << "k is " << k1 << " " << k2 << endl;
          if (p.s + w[j] <= k1) {
            dp[i] = min(dp[i], {p.f, p.s + w[j]});
          } else if (w[j] <= k2) {
            dp[i] = min(dp[i], {p.f + 1, w[j]});
          }
        }
      }
    }

//    cout << "dp of " << i << "=" << dp[i].f << "," << dp[i].s << endl;

    if (dp[i].f < ll(1e18))
      ans = max(ans, sum);
  }

  cout << ans << endl;

  return 0;
}