#include <bits/stdc++.h>
using i64 = long long;
#define REP(i, n) for (int i = 0, REP_N_ = int(n); i < REP_N_; ++i)
#define ALL(x) std::begin(x), std::end(x)

template <class T>
inline bool chmax(T &a, T b) {
  return a < b and ((a = std::move(b)), true);
}
template <class T>
inline bool chmin(T &a, T b) {
  return a > b and ((a = std::move(b)), true);
}

template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &a) {
  for (auto &x : a) is >> x;
  return is;
}

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  const int L = 100'000'000;

  int n, m;
  cin >> n >> m;
  vector<i64> w(n);
  cin >> w;
  vector<i64> vlmax(L + 1);
  i64 lmax = 0;
  i64 vmin = 1e9;
  REP(i, m) {
    i64 l, v;
    cin >> l >> v;
    chmax(vlmax[v], l);
    chmax(lmax, l);
    chmin(vmin, v);
  }
  if (vmin < *max_element(ALL(w))) {
    cout << -1 << endl;
    exit(0);
  }
  REP(i, L) { vlmax[i + 1] = max(vlmax[i], vlmax[i + 1]); }

  auto get_len = [&](i64 w) {
    if (w > L) return lmax;
    return vlmax[w - 1];
  };

  vector<int> camels(n);
  REP(i, n) { camels[i] = i; }

  i64 ans = (n - 1) * lmax;
  do {
    vector<i64> pos(n);
    pos[0] = 0;
    for (int i = 1; i < n; ++i) {
      i64 w_sub = w[camels[i]];
      for (int j = i - 1; j >= 0; --j) {
        w_sub += w[camels[j]];
        i64 len = get_len(w_sub);
        chmax(pos[i], pos[j] + len);
      }
    }
    chmin(ans, pos[n - 1]);
  } while (next_permutation(ALL(camels)));

  cout << ans << endl;
}

#include <bits/stdc++.h>
#define sz(a) a.size()
#define pb(a) push_back(a)
#define all(a) a.begin(),a.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;typedef long long ll;const ll mod=1e9+7;
#define inf 0x3f3f3f3f
const int M=1e4+7,N=4e5+7;
int T;

int n,m;
vector<int> va[N];
int cx[N],cy[N],dx[N],dy[N];
int u[N],v[N];
bool vis[N];
int nx,ny,k,dis;
bool searchpath()
{
	queue<int> q;
	dis=inf;
	memset(dx,-1,sizeof(dx));
	memset(dy,-1,sizeof(dy));
	for(int i=1;i<=nx;i++){
		if(cx[i]==-1){
			q.push(i);
			dx[i]=0;
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(dx[u]>dis) break;
		for(int i=0,vv;i<va[u].size();i++){
            vv=va[u][i];
			if(dy[vv]==-1){
				dy[vv]=dx[u]+1;
				if(cy[vv]==-1) dis=dy[vv];
				else{
					dx[cy[vv]]=dy[vv]+1;
					q.push(cy[vv]);
				}
			}
		}
	}
	return dis!=inf;
}
int find(int u)
{
	for(int i=0,vv;i<va[u].size();i++){
        vv=va[u][i];
		if(!vis[vv]&&dy[vv]==dx[u]+1){
			vis[vv]=1;
			if(cy[vv]!=-1&&dy[vv]==dis) continue;
			if(cy[vv]==-1||find(cy[vv])){
				cy[vv]=u;cx[u]=vv;
				return true;
			}
		}
	}
	return false;
}
int MaxMatch(){
	int res=0;
	memset(cx,-1,sizeof(cx));
	memset(cy,-1,sizeof(cy));
	while(searchpath()){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=nx;i++){
			if(cx[i]==-1){
				res+=find(i);
			}
		}
	}
	return res;
}
int main()
{
    scanf("%d",&n);
    k=nx=ny=n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&u[i],&v[i]);
        nx=ny=max(nx,max(u[i],v[i]));
        va[i].pb(u[i]);
        va[i].pb(v[i]);
        //va[u[i]].pb(v[i]);
    }
	printf("%d\n",MaxMatch());

    return 0;
}
/***
4
1 2
1 3
4 2
2 3

12
5 2
5 6
1 2
9 7
2 7
5 5
4 2
6 7
2 2
7 8
9 7
1 8


***/
