#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define eb emplace_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"LINE %d: (%s) = ",__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}

const ll MAXN=1e2+5,MAXlg=__lg(MAXN)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;
const int MAXM = 1e4+5;

vector<pii> edge;
int c[MAXN], ans[MAXM]; // 0:-> 1:<-
vector<pii> e[MAXN];
bool vis[MAXN];
void print(int x){
    if (x) cout << "<-" << endl;
    else cout << "->" << endl;
}
void dfs(int x){
    vis[x] = true;
    for (auto i:e[x]) {
        pii cur = edge[i.X];
        int to;
        if (i.Y == 0) to = cur.Y;
        else to = cur.X;
        ans[i.X] = i.Y;
        if (vis[to]) continue;
        dfs(to);
    }
}
signed main(){
    IOS();
    int n,m;
    cin >> n >> m;
    for (int i=0;i<m;++i) {
        int u,v;
        cin >> u >> v;
        u--, v--;
        edge.eb(u,v);
        ans[i] = -1;
    }
    for (int i=0;i<n;++i) cin >> c[i];
    for (int i=0;i<m;++i) {
        int u = edge[i].X, v = edge[i].Y;
        if (c[u] == c[v]) {
            e[u].eb(i,0);
            e[v].eb(i,1);
            continue;
        }
        if (c[u] > c[v]) ans[i] = 0;
        else ans[i] = 1;
    }
    for (int i=0;i<n;++i) {
        if (vis[i]) continue;
        dfs(i);
    }
    for (int i=0;i<m;++i) print(ans[i]);
}

#include <bits/stdc++.h>

using namespace std;

const int max_n = 11, inf = 1000111222;
const int max_m = 100011;

int n, m, a[max_n], dp[max_n][max_n];
pair<int, int> b[max_m];
vector<pair<int, int>> v;

int solve() {
    for (int i = 0; i < n; ++i) {
        if (a[i] > v[0].first) {
            return inf;
        }
    }
    for (int len = 1; len <= n; ++len) {
        for (int l = 0; l + len <= n; ++l) {
            const int r = l + len - 1;
            int tot = accumulate(a + l, a + r + 1, 0);
            auto it = upper_bound(v.begin(), v.end(), make_pair(tot, -1));
            dp[l][r] = 0;
            if (it != v.begin()) {
                --it;
                dp[l][r] = it->second;
            }
            for (int i = l + 1; i < r; ++i) {
                dp[l][r] = max(dp[l][r], dp[l][i] + dp[i][r]);
            }
            //cout << l << " " << r << ": " << dp[l][r] << endl;
        }
    }
    return dp[0][n - 1];
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i].second >> b[i].first;
    }
    sort(b, b + m);
    for (int i = 0; i < m; ++i) {
        if (v.empty() || v.back().second < b[i].second) {
            v.push_back(b[i]);
        }
    }
    sort(a, a + n);
    int ans = inf;
    do {
        ans = min(ans, solve());
    } while (next_permutation(a, a + n));
    if (ans == inf) {
        ans = -1;
    }
    cout << ans << "\n";
    return 0;
}
