#include <bits/stdc++.h>
#define ll long long 

using namespace std;

vector <int> vis;

void DFS(int x, vector <vector <int> > & g)
{
	vis[x] = 1;
	
	for (auto to: g[x])
		if (!vis[to])
			DFS(to, g);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	map <int, vector <pair <int, int> > > mp;
	mp[n].push_back({0, 0});
	
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		mp[y].push_back({x, i});
	}
	
	for (auto & x: mp)
		sort(x.second.begin(), x.second.end());
	
	vector <vector <int> > g(m + 1);
		
	for (auto & x: mp)
	{
		int ptr = 0;
		
		for (int i = 0; i < x.second.size(); i++)
		{
			while (ptr < mp[x.first + 1].size() && mp[x.first + 1][ptr].first <= x.second[i].first)
				ptr++;
				
			int save_ptr = ptr, right_border = (i == x.second.size() - 1 ? 2 * n + 1 : x.second[i + 1].first);
			
			while (ptr < mp[x.first + 1].size() && mp[x.first + 1][ptr].first <= right_border)
				ptr++;
				
			for (int j = save_ptr; j < ptr; j++)
				g[x.second[i].second].push_back(mp[x.first + 1][j].second);
		}
		
		ptr = 0;
		
		for (int i = 0; i < x.second.size(); i++)
		{
			while (ptr < mp[x.first - 1].size() && mp[x.first - 1][ptr].first <= x.second[i].first)
				ptr++;
				
			int save_ptr = ptr, right_border = (i == x.second.size() - 1 ? 2 * n : x.second[i + 1].first);
			
			while (ptr < mp[x.first - 1].size() && mp[x.first - 1][ptr].first <= right_border)
				ptr++;
				
			for (int j = save_ptr; j < ptr; j++)
				g[x.second[i].second].push_back(mp[x.first - 1][j].second);
		}
	}
	
	vis.resize(m + 1);
	DFS(0, g);
	int ans = 0;
	
	for (auto & x: mp)
		if (x.second.size() && vis[x.second.back().second])
			ans++;
			
	cout << ans;
}
#include<bits/stdc++.h>
using namespace std ;
using ll = long long ;
using vll = vector<ll> ;

int main(){
    int n,m ;
    cin >> n >> m ;
    vll a(n) ;
    for(auto &i:a) cin >> i ;
    vector<pair<ll,ll>> b(m) ;
    for(auto &i:b) cin >> i.second >> i.first ;
    sort(b.begin(),b.end()) ;
    b.emplace_back(1e10,0ll) ;
    for(int i=1;i<m;i++) b[i].second = max(b[i].second,b[i-1].second) ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        if(a[i]>b[j].first){
            cout << -1 << endl ;
            return 0 ;
        }
    }
    ll ans = 1e15 ;
    vector<int> c(n) ;
    for(int i=0;i<n;i++) c[i] = i ;
    do{
        vll d(n,0) ;
        for(int i=1;i<n;i++){
            ll sum = a[c[i]] ;
            for(int j=i-1;j>=0;j--){
                sum += a[c[j]] ;
                ll l=-1,r=m,mid ;
                while(l+1<r){
                    mid = (l+r)/2 ;
                    if(b[mid].first>=sum) r = mid ;
                    else l = mid ;
                }
                if(l<0) continue ;
                d[i] = max(d[i],d[j]+b[l].second) ;
            }   
        }
        // cout << ans << endl ;
        ans = min(ans,d[n-1]) ;
    }while(next_permutation(c.begin(),c.end())) ;
    cout << ans << endl ;
}