#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
const int mx = 100009;
const int inf = 22;

int heights[mx];
int values[inf];
int pieces[inf];
vector<int> boxes;


pair<int, int> dp[(1 << inf) + 99];

int main() {
  int h, t;
  scanf("%d%d", &h, &t);
  for (int i = 0; i < h; ++i) {
    scanf("%d", heights + i);
  }
  for (int i = 0; i < t; ++i) {
    scanf("%d%d", pieces + i, values + i);
  }
  bool impossible = false;
  int mx = 0;
  for (int i = 0; i < h; ++i) {
    if (heights[i] > t) {
      impossible = true;
      break;
    }
    if (mx < heights[i]) {
      mx = heights[i];
    }
  }
  if (impossible) {
    printf("0\n");
    return 0;
  }
  for (int store = 1; store <= mx; ++store) {
    int cur = 0;
    for (int i = 0; i < h; ++i) {
      if (heights[i] >= store) {
        cur++;
      } else if (cur > 0) {
        boxes.push_back(cur);
        cur = 0;
      }
    }
    if (cur > 0) {
      boxes.push_back(cur);
    }
  }
  if (boxes.size() > t || boxes.empty()) {
    printf("0\n");
    return 0;
  }


  dp[0] = { 0, 0 };

  for (int mask = 1; mask < (1 << t); mask++) {
    dp[mask] = make_pair(-1, 0);
    for (int i = 0; i < t; i++) {
      if (!((1 << i) & mask))
        continue;
      pair<int, int> option = dp[mask ^ (1 << i)];
      if (option.first == -1 || option.first==boxes.size()) {// not fully filled previous boxes
        continue;
      }
      if (option.second + pieces[i] < boxes[option.first]) {
        option.second += pieces[i];
        dp[mask] = option;
      } else if (option.second + pieces[i] == boxes[option.first]) {
        option.second = 0, option.first++;
        dp[mask] = option;
      }
    }
  }
  int best = 0;
  for (int mask = 1; mask < (1 << t); mask++) {
    if (dp[mask].first == boxes.size()) {
      int val = 0;
      for (int i = 0; i < t; i++) {
        if (((1 << i) & mask)) {
          val += values[i];
        }
      }
      if (best < val) {
        best = val;
      }
    }
  }
  printf("%d\n", best);
}