#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif
struct Cow{
	using D = int;
	const D inf = 1e9;
	struct Edge{
		int to;
		D cost;
		Edge(int to,D cost):to(to),cost(cost){}
	};
	int N,M;
	vector<vector<Edge>> G;
	vector<D> d;
	Cow(int N):N(N){
		G.assign(N,vector<Edge>());
		d.assign(N,inf);
	}
	void add_edge(int t,int s,D c){	// correspond to t-s <= c
//		printf("%d->%d   :%d\n",t,s,c);
		G[s].pb(Edge(t,c));
	}
	void add_edge(int t,int s,D clow,D chigh){	// clow <= t-s <= chigh
		add_edge(t,s,chigh);
		add_edge(s,t,-clow);
	}
	/*
		return the inequalities have a valid assignment
		if satisfiable, minimize d[T]-d[S]

		negative cycle    <=> unsatisfiable
		d[T] - d[S] = inf <=> feasible unboundedly

		d[S]=0

		Tによらなくない?(気づき)
	*/
	bool IsValidAssign(int S = 0){
		vector<int> prev(N);
		d[S] = 0;
		rep(ph,N){
			bool update = 0;
			int v = -1;
			rep(s,N) for(auto e:G[s]){
				int t = e.to;
				D cost = e.cost;
				if(d[s]+cost < d[t]){
					update=1;
					v = t;
					d[t] = d[s]+cost;
					prev[t] = s;
				}
			}
			if(ph == N-1 && update){
				// vector<int> path;
				// path.pb(v);
				// int u = v;
				// do{
				// 	show(u);
				// 	u = prev[u];
				// 	path.pb(u);
				// }while(u!=v);
				// reverse(all(path));
				// show(path);
				return 0;
			}
			if(!update) break;
		}
		return 1;
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N,M; cin >> N >> M;
	const int inf = 1e9;
	int ans = inf;
	V<int> w(N); rep(i,N) cin >> w[i];
	int mxw = *max_element(all(w));
	V<int> lim(1<<N,0);
	rep(i,M){
		int l,v; cin >> l >> v;
		if(v < mxw){
			cout << -1 << endl;
			return 0;
		}
		rep(s,1<<N){
			int sum=0;
			rep(j,N) if(s&1<<j) sum += w[j];
			if(sum > v) chmax(lim[s],l);
		}
	}
	show(lim);
	V<int> o(N); iota(all(o),0);
	do{
		Cow cow(N);
		rep(l,N) for(int r=l+1;r<N;r++){
			int s=0;
			for(int i=l;i<=r;i++) s|=1<<o[i];
			cow.add_edge(l,r,-lim[s]);
		}
		rep(i,N-1){
			cow.add_edge(i,i+1,0);
		}
		if(cow.IsValidAssign(N-1)){
			show(cow.d);
			chmin(ans,cow.d[N-1]-cow.d[0]);
		}
	}while(next_permutation(all(o)));
	if(ans == inf) cout << -1 << endl;
	else cout << ans << endl;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
#define endl '\n'
#define lowbit(x) (x & -x)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define ck(x) (x >= mod ? x - mod : x)
#define inf 0x3f3f3f3f
#define eps 1e-6
#define maxn 1500010
#define maxm 1010
#define G 3
#define invG 332748118
const int mod = 998244353;
const double PI = 4 * atan2(1.0, 1.0);
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
    int operator()(pair<int, int> x) const { return x.first ^ x.second ^ RANDOM; }
};
int n, m, a[maxn], cnt[maxn], p, ans = inf;
set<int> s;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    s.insert(0);
    for (int i = 1; i < m; i++) {
        cnt[a[i]]++;
        if (s.count(a[i]))s.erase(a[i]);
        if (cnt[a[i] + 1] == 0)s.insert(a[i] + 1);
    }
    for (int i = m; i <= n; i++) {
        cnt[a[i]]++;
        if (s.count(a[i]))s.erase(a[i]);
        if (cnt[a[i] + 1] == 0)s.insert(a[i] + 1);
//        cout << i << ":";
//        for (auto &u:s)cout << u << ' ';
//        cout << endl;
        ans = min(ans, *s.begin());
        cnt[a[i - m + 1]]--;
        if (cnt[a[i - m + 1]] == 0 && s.count(a[i - m + 1] + 1))s.erase(a[i - m + 1] + 1);
        if (a[i - m + 1] > 0 && cnt[a[i - m + 1] - 1] != 0)s.insert(a[i - m + 1]);
        if (cnt[0] == 0)s.insert(0);
    }
    cout << ans << endl;
    return 0;
}