// submasks taken from https://cp-algorithms.com/algebra/all-submasks.html

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef long long ll;
const int mod = 1e9 + 7;

int a[18], D[17], I[17], party_I[1 << 17], party_D[1 << 17];
int dp[17][1 << 17];
int n, t, s;
vector <int> max_days;

int f(int i, int mask) {
  if (i == s) return 0;
  if (dp[i][mask] != -1) return dp[i][mask];
  int ret = 0;
  for (int submask = mask; submask; submask = (submask - 1) & mask) {
    if (party_D[submask] <= max_days[i]) {
      ret = max(ret, party_I[submask] + f(i + 1, mask ^ submask));
    }
  }
  return dp[i][mask] = ret;
}


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

  cin >> n >> t;
  s = min(n, t);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x != 0) {
      a[0] += 1;
      a[min(x, s) + 1] -= 1;
    }
    if (x == 0 || i == n - 1) {
      for (int j = 1; j <= s; j++) {
        a[j] += a[j - 1];
        max_days.push_back(a[j]);
      }
      memset(a, 0, sizeof a); 
    }
  }
  for (int i = 0; i < t; i++) {
    cin >> D[i] >> I[i];
  }

  for (int mask = 0; mask < (1 << t); mask++) {
    for (int k = 0; k < t; k++) {
      if (mask & (1 << k)) {
        party_I[mask] += I[k];
        party_D[mask] += D[k];
      }
    }
  }

  sort(all(max_days));
  reverse(all(max_days));

  memset(dp, -1, sizeof dp);
  cout << f(0, (1 << t) - 1);
}