#include <stdio.h>
#include <assert.h>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <string.h>
#include <string>
#include <vector>
#include <numeric>
#include <iomanip>
#define ll long long
#define mint modint<MOD>
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tpiii tuple<int,int,int>
#define mp make_pair
#define mt make_tuple
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector
#define vi vec<int>
#define vmi vec<mint>
#define vl vec<ll>
#define vvi vec<vi>
#define vvl vec<vl>
#define vpii vec<pii>
#define vpll vec<pll>
#define vbl vec<bool>
#define endl "\n"
#define all(c) (c).begin(),(c).end()
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
string stin(){string s;cin>>s;return s;}
char chin(){char c;cin>>c;return c;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void drop(string s){cout<<s<<endl; exit(0);}
void drop(int x){cout<<x<<endl; exit(0);}
void drop(ll x){cout<<x<<endl; exit(0);}
void drop(double x){cout<<x<<endl; exit(0);}

int n;
vi p,x;
vvi ans;

bool f(int k,int q){ //k回目
    if(k==n-1){
        return (p[n-1]==0) ^ (q!=0 && q!=x[n-1]);
    }
    if(ans[k+1][q*10%7] < 0) ans[k+1][q*10%7] = f(k+1,q*10%7);
    if(ans[k+1][(q*10+x[k+1])%7] < 0) ans[k+1][(q*10+x[k+1])%7] = f(k+1, (q*10+x[k+1])%7);
    if(p[k] == 0){
        return ans[k+1][q*10%7] || ans[k+1][(q*10+x[k+1])%7];
    }else{
        return !(ans[k+1][(q*10+x[k+1])%7]  && ans[k+1][(q*10+x[k+1])%7]);
    }
}

int main(){
    n=in();
    string s=stin();
    x.resize(n);
    rep(i,n)x[i] = (s[i]-'0')%7;
    s=stin();
    p.resize(n);
    rep(i,n)p[i]=s[i]=='T' ? 1:0; // 1 -> T, 0 -> A
    vi m(n);
    m[n-1]=1;
    rep3(k,n-2,0)m[k] = m[k+1] * 10 % 7;
    
    ans.resize(n,vi(7,-1));
    rep(q,7){
        if(p[n-1] == 1){
            ans[n-1][q] =  q==0 || q==x[n-1];
        }else{
            ans[n-1][q] =  q == 0 && q==x[n-1];
        }
    }
    rep3(k,n-2,0){
        rep(q,7){
            if(p[k] == 1){
                ans[k][q] =  ans[k+1][q] || ans[k+1][((q - x[k]*m[k])%7+7)%7];
            }else{
                ans[k][q] =  ans[k+1][q]  && ans[k+1][((q - x[k]*m[k])%7+7)%7];
            }
        }
    }
    if(ans[0][0])drop("Takahashi");
    else drop("Aoki");
}
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

const ll INF=1e15;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N,M;
  cin>>N>>M;
  vector<ll> W(N);
  rep(i,N) cin>>W[i];
  vector<ll> L(M),V(M);
  rep(i,M) cin>>L[i]>>V[i];

  {
    ll mi=*min_element(all(V));
    ll ma=*max_element(all(W));
    if(mi<ma){
      cout<<"-1"<<"\n";
      return 0;
    }
  }

  vector<ll> v=L;
  sort(all(v));
  v.erase(unique(all(v)),v.end());
  int P=v.size();
  map<ll,int> mp;
  rep(i,P) mp[v[i]]=i;

  vector<ll> dp(P+1,INF);
  rep(i,M) chmin(dp[mp[L[i]]],V[i]);
  for(int i=P-1;i>=0;i--) chmin(dp[i],dp[i+1]);

  ll MA=*max_element(all(L));
  vector<int> ord(N,0);
  rep(i,N) ord[i]=i;
  ll ans=INF;
  do{
    vector<ll> dist;
    vector<ll> sum;
    sum.push_back(0);
    for(int i=0;i<N;i++){
      int now=ord[i];
      ll ok=MA,ng=-1;
      while(abs(ok-ng)>1){
        ll mid=(ok+ng)/2;

        ll d=mid;
        ll w=W[now];
        bool dame=false;
        for(int j=i-1;j>=0;j--){
          int tar=ord[j];
          ll nw=w+W[tar];
          int z=upper_bound(all(v),d)-v.begin();
          if(dp[z]<nw){
            dame=true;
            break;
          }
          d+=dist[j];
          w=nw;
        }
        if(dame) ng=mid;
        else ok=mid; 
      }

      dist.push_back(ok);
    }
    ll res=0;
    rep(i,dist.size()) res+=dist[i];
    chmin(ans,res);
  }while(next_permutation(all(ord)));

  cout<<ans<<endl;

  return 0;
}
