#include <bits/stdc++.h>
//#include <atcoder/modint>
//#include <atcoder/math>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//using mint = modint998244353;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;   
  
int main(){
  //using namespace std;
  
  int n, m;
  cin>>n>>m;
  vector<long long> w(n);
  REP(i, n) cin>>w[i];
  vector<long long> l(m), v(m);
  REP(i, m) cin>>l[i]>>v[i];
  
  long long min_v = INF;
  REP(i, m) if(v[i] < min_v) min_v = v[i];
  //cout << "min_v = " << min_v << endl;
  long long max_w = -1;
  REP(i, n) max_w = max(max_w, w[i]);
  if(max_w > min_v){
    cout << -1 << endl;
    return 0;
  }
  
  typedef pair<long long, long long> P;
  auto cmp = [](P p, P q) -> bool {
    return p.second < q.second;
  };
  {
    vector<P> vec;
    REP(i, m) vec.emplace_back(l[i], v[i]);
    sort(ALL(vec), cmp);
    REP(i, m){
      l[i] = vec[i].first;
      v[i] = vec[i].second;
    }
  }
  //REP(i, m) cout << l[i] << " " << v[i] << endl;
  vector<long long> dl(m);
  REP(i, m){
    if(i == 0) dl[i] = l[i];
    else dl[i] = max(l[i], dl[i - 1]);
  }
  
  sort(ALL(w));
  long long ans = INF;
  do {
    vector<long long> dw(n);
    REP(i, n){
      if(i == 0) dw[i] = w[i];
      else dw[i] = w[i] + dw[i - 1];
    }
    vector<vector<long long>> x(n, vector<long long>(n, 0));
    REP(i, n){
      REP(j, n){
        if(i > j) continue;
        //i <= j
        if(i == j) continue;
        //i < j
        long long cw;
        if(i > 0) cw = dw[j] - dw[i - 1];
        else cw = dw[j];
        int idx = lower_bound(ALL(v), cw) - v.begin();
        if(idx == 0) continue;
        x[i][j] = max(x[i][j], dl[idx - 1]);
      }
    }
        
    vector<long long> dp(n);
    REP(i, n){
      if(i == 0) continue;
      long long temp = 0;
      for(int j = 0; j <= i; j++){
        temp = max(temp, dp[j] + x[j][i]);
      }
      dp[i] = temp;
    }
    
    ans = min(ans, dp[n - 1]);
  } while (next_permutation(ALL(w)));
  
  cout << ans << endl;
  
  return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define hi ios_base::sync_with_stdio;cin.tie(NULL);cin.tie(NULL);
typedef long long int ll;
typedef long double ld;
typedef long long unsigned llu;
#define test				int test; cin>>test; while(test--)
#define loop(i,n,k) 		for(int i=n;i<k;i++)
#define rloop(i,n,k) 		for(int i=n;i>=k;i--)
#define INT(a) 				int a;scanf("%d",&a);
#define intin(temp)			scanf("%d",&temp);
#define longin(temp)		scanf("%lld",&temp);
#define LLI(a) 				ll a;scanf("%lld",&a);
#define DOUBLE(a) 			double a;scanf("%f",&a);
#define LD(a) 				long double a;scanf("%lf",&a);
#define pb(i) 				push_back(i);
#define sz(i) 				i.size()
#define mkp(i,j)			make_pair(i,j);
#define ip 					pair<int,int>
#define dp					pair<ll,ll>
#define FOR(i,n)			for(i=0;i<n;i++)
#define range(v)			v.begin(),v.end()
#define bye					return 0;
#define file				freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
//===============================================================================================================
//Author:- Absolute_looser
//Class :- loosers
//===============================================================================================================
template<class c>
c gcd (c a,c b){
	if(b==0)
		return a;
	gcd(b,a%b);
}template<class a>
bool prime(a n){
	for(a i=2;i<=sqrt(n);i++){
		if(n%i==0)
			return 0;
	}
	return 1;
}
bool bigger(pair<int,int>picachu,pair<int,int> qicachu){
	return (picachu.first<qicachu.first);
}void printarr(int arr[],int n){
	for(int i=0;i<n;i++)
		cout<<arr[i]<<' ';
	cout<<endl;
}
int chartoint(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 26;
    return 52;
}
int kadane(int arr[],int n){
	int maximum= arr[0];
	int max_so_far = 0;
	for(int i=0;i<n;i++){
		max_so_far+=arr[i];
		if(max_so_far>maximum)
			maximum = max_so_far;
		if(max_so_far<0)
			max_so_far = 0;
	}
	return maximum;
}
int a[200004];
ll div(ll x,ll n,ll m){
	ll ans =1 ;
	while(n){
		if(n&1){
			ans = ans*x%m;
		}
		x = x*x%m;
		n >>=1;
	}
	return ans;
}
void run(){	
	ll n;
	ll m;
	cin >> n;
	cin >> m;
	cout << div(10,n,m*m)/m<< endl;
}
int main(){
	hi;
	#ifndef ONLINE_JUDGE 
   	freopen("input.txt", "r", stdin); 
  	freopen("error.txt", "w", stderr); 
  	freopen("output.txt", "w", stdout); 
   	#endif 
   
  
   	{ 
      	run(); 
   	}
  	cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
 	bye;
}