#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> w(n);
    ll max_w = 0LL;
    for(int i=0;i<n;++i) {
        cin >> w[i];
        max_w = max(max_w, w[i]);
    }

    vector<Pll> wl(m); // {重さ制限, 長さ}
    ll min_lim_w = LINF;
    for(int i=0;i<m;++i) {
        cin >> wl[i].second >> wl[i].first;
        min_lim_w = min(min_lim_w, wl[i].first);
    }
    sort(wl.begin(), wl.end());

    if(max_w > min_lim_w) {
        cout << -1 << endl;
        return 0;
    }

    set<Pll> st; // {長さ, 重さ制限}
    set<Pll> st2; // {重さ制限, 長さ}
    // 重さ制限はは今見てる奴が1番緩いはずなので、今まで見た長さで最長だった場合だけ入れる。
    st.emplace(wl[0].second, wl[0].first);
    st2.insert(wl[0]);
    for(int i=1;i<m;++i) {
        if(wl[i].second <= 0LL) continue;
        ll l_max = st.rbegin()->first;
        if(l_max < wl[i].second) {
            st.emplace(wl[i].second, wl[i].first);
            st2.insert(wl[i]);
        }
    }
    
    vector<int> v(n);
    for(int i=0;i<n;++i) v[i] = i;

    ll ans = LINF;
    do {
        vector<ll> ws(n+1, 0LL);
        ws[0] = 0LL;
        for(int i=0;i<n;++i) {
            ws[i+1] = ws[i] + w[v[i]];
        }

        vector<ll> xs(n, -1LL);
        xs[0] = 0LL;
        for(int i=1;i<n;++i) {
            ll ng = xs[i-1]-1LL, ok = LINF;
            while(ok - ng > 1LL) {
                ll mid = (ok + ng) / 2;
                bool isok = true;
                for(int j=0;j<i;++j) {
                    auto itr = st.lower_bound(Pll(mid - xs[j] + 1, -LINF));
                    if(itr == st.end()) continue;
                    if(ws[i+1] - ws[j] > (itr->second)) {
                        isok = false;
                        break;
                    }
                }
                if(isok) {
                    ok = mid;
                } else {
                    ng = mid;
                }
            }
            xs[i] = ok;
        }
        // for(int i=0;i<n-1;++i) cerr << xs[i] << " ";
        // cerr << xs[n-1] << endl;
        ans = min(ans, xs[n-1]);
    } while(next_permutation(v.begin(), v.end()));

    cout << ans << endl;
}
// First of all Naste "_" 
// Always check the fast IO is there or not
// always write functions for little things coz u repeat the variables

#include<bits/stdc++.h>
#include <algorithm> 
using namespace std;

typedef long long int ll;

#define endline '\n'
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>
#define pb push_back
#define fr(i,a,b) for(ll i=a;i<(ll)b;i++)
#define rfr(i,a,b) for(int i=a;i>=(int)b;i--)
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
const int N = 29;
const ll mod=1e9+7;

ll mod_exp(ll x,ll y)
{
    if(y<=0)
        return(1);
    else if(y%2==0)
        return(mod_exp((x*x),y/2));
    else
        return((x*mod_exp((x*x),(y-1)/2)));
}

int visi[N];
vi v[N];
int col[N];
int lvl[N];
int dfs(int node)
{
	visi[node]=1;
	int ans1=1;
	for(int it:v[node])
	{
		if(lvl[it]!=0&&lvl[it]!=lvl[node]+1)
		{
			if(col[it]==col[node])
			{
				ans1=0;
			}
			continue;
		}
		lvl[it]=lvl[node]+1;
		ll temp=0;
		fr(i,1,4)
		{
			if(i!=col[node])
			{
				col[it]=i;
				temp+=dfs(it);
				col[it]=0;
			}
		}
		ans1*=temp;
	}
	return ans1;
}
void clear()
{
	fr(i,0,N)
	{
		v[i].clear();
		visi[i]=0;
		col[i]=0;
		lvl[i]=0;
	}
}
int main()
{
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    // freopen("debug.txt", "w", stderr);
    #endif
    int t=1; 
    // cin>>t;
    while(t--)
    {
    	clear();
    	int n,m; cin>>n>>m;
    	if(m==0)
    	{
    		cout<<mod_exp(3,n);
    		return 0;
    	}
    	while(m--)
    	{
    		int x,y; cin>>x>>y;
    		v[x].pb(y),v[y].pb(x);
    	}
    	// ll c=0;
    	ll ans=1;
    	fr(i,1,n+1)
    	{
    		if(visi[i]==0)
    		{
    			col[i]=1;lvl[i]=1;
    			ans*=3*dfs(i);
    		}
    	}
    	cout<<ans<<endline;
    }

    #ifndef ONLINE_JUDGE
    cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
    #endif
    
}