#include<bits/stdc++.h>
using namespace std;
int h , T;
int c[100005];
int d[17] , I[17];
int f[17][1<<16];
int sum[1<<16] ;
int sumI[1<<16];
int main()
{
   // freopen("in.txt","r",stdin) ;
    ios::sync_with_stdio(false) ; cin.tie(0) ;cout.tie(0) ;
    cin >> h >> T;
    for(int i = 1;i <= h;i++) {
        cin >> c[i];
        if(c[i] > T) {
            cout << 0 << '\n' ; return 0;
        }
    }
    for(int i = 1;i <= T;i++) cin >> d[i] >> I[i] ;
    vector<int> vs;
    for(int i = T;i >= 1;i--) {
        int lst = 1;
        for(int j = 2;j <= h + 1;j++) {
            if((c[j] >= i) != (c[j - 1] >= i) || j == h + 1) {
                if(c[j - 1] >= i) {
                    vs.push_back(j - lst) ;
                }
                lst = j;
            }
        }
    }
    if(vs.size() > T) {
        cout << 0 ; return 0;
    }
    for(int i = 1;i < (1<<T);i++) {
        for(int j = 0;j < T;j++) {
            if((i >> j) & 1) {
                sum[i] = sum[i ^ (1<<j)]+d[j + 1] ;
                sumI[i] = sumI[i ^ (1<<j)]+I[j+1];
                break ;
            }
        }
    }
    for(int i = 1;i <= vs.size();i++) {
        for(int j = 0;j < (1<<T);j++) {
            f[i][j] = -1e9;
            for(int s = j ;s ; s = (s - 1) & j) { ///what I use
                if(sum[s] == vs[i - 1]) {
                    f[i][j] = max(f[i][j] , f[i - 1][j ^ s] + sumI[s]) ;
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i < (1<<T);i++) ans = max(ans , f[vs.size()][i]) ;
    cout << ans ; return 0;
}