#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define _ << " _ " <<

template<class> struct is_container : false_type {};
template<class... Ts> struct is_container<vector<Ts...>> : true_type {};
template<class... Ts> struct is_container<map<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_map<Ts...>> : true_type {};
template<class... Ts> struct is_container<set<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_set<Ts...>> : true_type {};
template<class... Ts> struct is_container<multiset<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_multiset<Ts...>> : true_type {};
template<class T, class = typename enable_if<is_container<T>::value>::type>
ostream& operator<<(ostream &o, T x) {
  int f = 1;
  o << "{";
  for (auto y : x) {
    o << (f ? "" : ", ") << y;
    f = 0;
  }
  return o << "}";
}
template<class T, class U>
ostream& operator<<(ostream &o, pair<T, U> x) {
  return o << "(" << x.first << ", " << x.second << ")";
}

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int MAX = 16;
const int INF = 1e9;

void no() {
    cout << "0\n";
    exit(0);
}

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

    int h, t;
    cin >> h >> t;
    vi l, cur_l(MAX);
    for (int i = 0; i <= h; i++) {
        int c;
        if (i == h) c = 0;
        else cin >> c;

        if (c > MAX) no();

        for (int j = 0; j < MAX; j++) {
            if (j < c) cur_l[j]++;
            else {
                if (cur_l[j] > 0) l.push_back(cur_l[j]);
                cur_l[j] = 0;
                if (l.size() > MAX) no();
            }
        }
    }

    vi cost(1 << t), len(1 << t);
    for (int i = 0; i < t; i++) {
        int d, c;
        cin >> d >> c;

        for (int mask = 0; mask < (1 << i); mask++) {
            cost[mask ^ (1 << i)] = cost[mask] + c;
            len[mask ^ (1 << i)] = len[mask] + d;
        }
    }

    vector<vi> groups(h + 1);
    for (int mask = 0; mask < (1 << t); mask++)
        if (len[mask] <= h) groups[len[mask]].push_back(mask);

    int m = l.size();
    assert(m <= MAX);
    vector<vi> dp(m + 1, vi(1 << t));
    for (int i = 0; i < m; i++) 
        for (int mask = 0; mask < (1 << t); mask++)  {
            dp[i + 1][mask] = -INF;
            for (int group : groups[l[i]])
                if ((mask | group) == mask)
                    dp[i + 1][mask] = max(dp[i + 1][mask], dp[i][mask ^ group] + cost[group]);
            if (dp[i + 1][mask] < 0) dp[i + 1][mask] = -INF;
        }

    int sol = max(0, *max_element(dp.back().begin(), dp.back().end()));
    cout << sol << '\n';

    return 0;
}