#include <bits/stdc++.h>
#define N 200005
#define M 20
using namespace std;
int n, m;
int a[N];
struct zero
{
  int len, val;
  friend bool operator<(zero a, zero b) { return a.len > b.len; }
} lib[M];
priority_queue<int, vector<int>, greater<int>> q;
int siz = 0, B;
int upper = 0;
int aux[M];

int ans = 0;
void dfs(int i, int s, int w) {
  if (i == siz + 1) {
    ans = std::max(ans, w);
    return;
  }

  int tot = 0, vaild[M];
  for (int j = 0; j < m; j++) if (s >> j & 1)
    vaild[tot ++] = j;
  
  for (int t = (1 << tot) - 1; t >= 0; t--) {
    int len_s = 0;
    int val_s = 0;
    int sn = s;
    for (int j = 0; j < tot && len_s <= aux[i]; j++) if (t >> j & 1) {
      len_s += lib[vaild[j]].len;
      val_s += lib[vaild[j]].val;
      sn ^= (1 << vaild[j]);
    }
    if (len_s > aux[i]) continue;

    dfs(i + 1, sn, w + val_s);
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    upper = max(upper, a[i]);
  }
  a[n + 1] = 0;
  for (int u = 1; u <= min(upper, m); u++) {
    int las = 0;
    for (int i = 1; i <= n + 1; i++) if (a[i] < u) {
      int nwlen = i - 1 - las;
      if (siz == m) {
        if (q.top() < nwlen)
          q.pop(), q.push(nwlen);
      } else {
        siz++;
        q.push(nwlen);
      }
      las = i;
    }
  }
  for (int i = 1; i <= siz; i++)
  {
    aux[i] = q.top();
    q.pop();
  }
  for (int i = 0; i < m; i++)
    scanf("%d%d", &lib[i].len, &lib[i].val);
  
  dfs(1, (1 << m) - 1, 0);
  printf("%d\n", ans);
  return 0;
}