#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
vector<int> boxes;
vector<pair<int,int>> items; // {rozmiar, value}

const int nax = 16;
bool dp[nax + 1][1 << nax];

int waga[1 << nax];
int wart[1 << nax];

void prep()
{
    int a,t;
    cin>>a>>t;
    vector<int> tab(a);
    for(int x=0;x<a;x++)
        cin>>tab[x];
    vector<int> v;
    for(int x=1;x<=t;x++)
    {
        int cnt = 0;
        for(int y=0;y<a;y++)
        {
            if(tab[y] >= x)
                cnt++;
            else if(cnt > 0)
            {
                v.push_back(cnt);
                cnt = 0;
            }
        }
        if(cnt > 0)
            v.push_back(cnt);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    while(v.size() > t)
        v.pop_back();
    boxes = v;
    while(t--)
    {
        int c,d;
        cin>>c>>d;
        items.push_back({c,d});
    }


    int pude = boxes.size();
    int itki = items.size();
    for(int i=0;i<(1<<itki);i++){
        int sumR = 0;
        int sumV = 0;
        for(int j=0;j<itki;j++){
            if((1 << j) & i){
                sumR += items[j].st;
                sumV += items[j].nd;
            }
        }
        waga[i] = sumR;
        wart[i] = sumV;
    }

    for(int i=0;i<(1<<nax);i++) dp[0][i] = false;
    dp[0][0] = true;
    for(int i=1;i<=pude;i++){
        int rozmiar = boxes[i - 1];
        for(int mask=0;mask<(1<<itki);mask++){
            int s = mask;
            while(s > 0){
                if(waga[s] <= rozmiar && dp[i - 1][mask ^ s]) dp[i][mask] = true;
                s = (s-1) & mask;
            }
            // also 0 X D
            if(dp[i - 1][mask]) dp[i][mask] = true;
        }
    }
    int ans = 0;
    for(int i=0;i<(1<<itki);i++){
        if(dp[pude][i]){
            ans = max(ans, wart[i]);
        }
    }
    cout << ans << "\n";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    prep();

    return 0;
}