#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const int INF = INT_MAX / 2;

vector<int> as;

int main(void) {
    int N, M;
    cin >> N >> M;

    as.push_back(0);
    for (int i = 0; i < M; i++) {
        int a;
        cin >> a;
        as.push_back(a);
    }
    as.push_back(N + 1);

    sort(as.begin(), as.end());

    int max_interval = INF;
    for (int i = 0; i < (int) as.size() - 1; i++) {
        int l = as[i];
        int r = as[i + 1];
        int interval = r - l - 1;
        if (interval > 0) {
            chmin(max_interval, interval);
        }
    }

    int ans = 0;
    for (int i = 0; i < (int) as.size() - 1; i++) {
        int l = as[i];
        int r = as[i + 1];
        int interval = r - l - 1;
        if (interval > 0) {
            ans += (interval + max_interval - 1) / max_interval;
        }
    }
    cout << ans << endl;

    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int M=1e5+5,N=(1<<8)+5;
int n,m,v[M],w[M],a[20],l[N],b[20],ans=998244353,f[N];
int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,n) scanf("%d",a+i);
	rep(i,1,m) scanf("%d%d",v+i,w+i);
	int S=(1<<n)-1;
	rep(i,1,S){
		int sum=0;
		rep(j,1,n) if((i>>(j-1))&1) sum+=a[j];
		rep(j,1,m) if(sum>w[j]) l[i]=max(l[i],v[j]);
	}
	rep(i,1,n) rep(j,1,m) if(a[i]>w[j]) return puts("-1"),0;
	rep(i,1,n) b[i]=i;
	do{
		f[0]=0;
		rep(i,2,n){
			int s=1<<b[i]-1; f[i]=0;
			per(j,i-1,1) s|=1<<b[j]-1,f[i]=max(f[i],f[j]+l[s]);
		}
		ans=min(ans,f[n]);
	}while(next_permutation(b+1,b+n+1));
	printf("%d",ans);
	return 0;
}
