#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define X first
#define Y second
#define PR std::pair
#define MP std::make_pair
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

int dp[1<<16][17];
int s[1<<16];
int s2[1<<16];
constexpr int INF = 1000666666;

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

    int n, t;
    std::cin >> n >> t;
    assert(t <= 16);
    VI A(n);
    FOR(i, n){
        std::cin >> A[i];
    }

    if(*std::max_element(A.begin(), A.end()) > t){
        std::cout << 0 << "\n";
        return 0;
    }

    VI mam;
    ll sum = 0;
    REP(store, 1, t+1){
        int pos = 0;
        while(pos < n){
            int have = 0;
            while(pos < n && A[pos] >= store){
                have++;
                pos++;
            }
            if(have > 0){
                mam.push_back(have);
                sum += have;
            }
            pos++;
        }
    }

    // TRAV(x, mam) std::cout << x << " ";
    // std::cout << std::endl;

    if(SZ(mam) > t){
        std::cout << 0 << "\n";
        return 0;
    }

    n = SZ(mam);

    std::vector<PII> teams;
    FOR(i, t){
        int a, b;
        std::cin >> a >> b;
        teams.push_back(MP(a, b));
        sum -= a;
    }

    if(sum > 0){
        std::cout << 0 << "\n";
        return 0;
    }

    FOR(i, 1<<t) FOR(j, n+1) dp[i][j] = -INF;
    dp[(1<<t)-1][0] = 0;

    FOR(i, 1<<t){
        int heh = 0;
        int val = 0;
        FOR(j, t){
            if(i & (1<<j)){
                heh += teams[j].X;
                val += teams[j].Y;
            }
        }
        s[i] = heh;
        s2[i] = val;
    }


    FOR(i, n){
        FOR(mask, 1<<t){
            for(int submask = mask; ; submask = (submask - 1) & mask) {
                if(s[submask] == mam[i]){
                    int cand = dp[mask][i] + s2[submask];
                    if(cand > dp[mask ^ submask][i+1]){
                        dp[mask ^ submask][i+1] = cand;
                    }
                }
                if(submask == 0) break;
            }
        }
    }

    int mx = -INF;
    FOR(mask, 1<<t){
        mx = std::max(mx, dp[mask][n]);
    }

    if(mx < 0) std::cout << 0 << "\n";
    else std::cout << mx << "\n";

    return 0;
}