#include<bits/stdc++.h> 
using namespace std;
namespace Ruri{
    #define ms(a,b) memset(a,b,sizeof(a))
    #define repi(i,a,b) for(int i=a,bbb=b;i<=bbb;++i)//attention reg int or reg ll ?
    #define repd(i,a,b) for(int i=a,bbb=b;i>=bbb;--i)
    #define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
    #define ce(i,r) i==r?'\n':' '
    #define pb push_back 
    #define all(x) x.begin(),x.end()
    #define gmn(a,b) a=min(a,b)
    #define gmx(a,b) a=max(a,b)
    #define fi first
    #define se second                         
    typedef long long ll;
    typedef unsigned long long ull;
    typedef double db;
    const int infi=1e9;//infi较大，注意涉及inf相加时爆int
    const ll infl=4e18;
    inline ll ceil_div(ll a,ll b){ return (a+b-1)/b; }
    inline ll pos_mod(ll a,ll b){ return (a%b+b)%b; }
    //std::mt19937 rnd(time(0));//std::mt19937_64 rnd(time(0));
}
using namespace Ruri;
namespace Read{
    #define ss(a) scanf("%s",a)
    inline int ri(){ int x; scanf("%d",&x); return x; }
    inline ll rl(){ ll x;  scanf("%lld",&x); return x; }
    inline db rd(){ db x; scanf("%lf",&x); return x; }
}
namespace DeBug{
    #define pr(x) cout<<#x<<": "<<(x)<<endl
    #define pra(x,a,b) cout<<#x<<": "<<endl; \
            repi(i,a,b) cout<<x[i]<<" ";     \
            puts("");   
    #define FR(a) freopen(a,"r",stdin)
    #define FO(a) freopen(a,"w",stdout)
}
using namespace Read;
using namespace DeBug;
const ll mod=1e9+7;
ll qpow(ll x,ll n,ll mod){ ll res=1;while(n){ if(n&1) res=(res*x)%mod; x=x*x%mod,n>>=1; } return res; }
struct Matrix{
	ll l,c,a[105][105];
	Matrix(ll _l=0,ll _c=0){ l=_l,c=_c,init_zero(); }
	void init_zero(){ repi(i,1,l)repi(j,1,c)	a[i][j]=0; }
	Matrix operator + (const Matrix x){ repi(i,1,l)repi(j,1,c) a[i][j]=(a[i][j]+x.a[i][j])%mod; return *this; } 
	Matrix operator - (const Matrix x){ repi(i,1,l)repi(j,1,c) a[i][j]=(a[i][j]-x.a[i][j]+mod)%mod; return *this; } 
	Matrix operator * (const Matrix x)
	{
		Matrix C(l,x.c);
		repi(i,1,l)repi(k,1,x.l)if(a[i][k])repi(j,1,x.c) 
			C.a[i][j]=(C.a[i][j]+a[i][k]*x.a[k][j])%mod;
		return C;
	}
	Matrix operator ^ (ll n)
	{
		Matrix A=(*this),B(l,c);
		repi(i,1,l)	B.a[i][i]=1;
		while(n){
			if(n&1)	B=B*A;
			A=A*A,n>>=1;
		}
		return B;
	}
	Matrix operator = (const Matrix x)
	{
		l=x.l,c=x.c;
		repi(i,1,l)repi(j,1,c) a[i][j]=x.a[i][j];
		return *this;
	}
    void neg_to_pos(){ repi(i,1,l)repi(j,1,c) a[i][j]=(a[i][j]%mod+mod)%mod; }
	void print(){ repi(i,1,l)repi(j,1,c) printf("%10.lld%c",a[i][j],ce(j,c)); puts(""); }
};
int n,m,k;
ll a[105];
int deg[105];
bool g[105][105];
int main()
{
	n=ri(),m=ri(),k=ri();
	ll invm=qpow(m,mod-2,mod),inv2m=qpow(2*m,mod-2,mod);
	Matrix ans(n,1);
	repi(i,1,n) a[i]=ans.a[i][1]=rl();

	repi(i,1,m){
		int u=ri(),v=ri();
		g[u][v]=g[v][u]=true;
		++deg[u],++deg[v];
	}
	
	Matrix trans(n,n);
	trans.init_zero();
	repi(i,1,n)repi(j,1,n)if(i==j||g[i][j]){
		if(i==j) trans.a[i][j]=(1ll*(m-deg[i])%mod*invm%mod+1ll*deg[i]%mod*inv2m%mod)%mod;
		else trans.a[i][j]=inv2m;
	}
	trans=trans^k;
	ans=trans*ans;
	repi(i,1,n) printf("%lld\n",ans.a[i][1]);


    return 0;
}

/**
 *    author:  otera    
**/
#include<iostream>
#include<string> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm> 
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<cassert>
#include<array>
using namespace std;

#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void solve() {
	int n, m; cin >> n >> m;
    vector<int> w(n);
    rep(i, n) {
        cin >> w[i];
    }
    vector<int> l(m), v(m);
    map<int, int> mp;
    vector<int> vs;
    int vmi = inf;
    rep(i, m) {
        cin >> l[i] >> v[i];
        chmin(vmi, v[i]);
        mp[v[i]] = max(l[i], mp[v[i]]);
        vs.push_back(v[i]);
    }
    rep(i, n) {
        if(w[i] > vmi) {
            cout << -1 << endl;
            return;
        }
    }
    vs.push_back(inf);
    mp[inf] = inf;
    sort(all(vs));
    vs.erase(unique(all(vs)), vs.end());
    int sz = (int)vs.size();
    vector<int> lma(sz + 1, 0);
    rep(i, sz) {
        lma[i + 1] = mp[vs[i]];
        // cerr << lma[i + 1] << endl;
        chmax(lma[i + 1], lma[i]);
    }
    vector<int> ids(n);
    iota(all(ids), 0);
    int ans = inf;
    do {
        vector<int> a(n);
        rep(i, n) a[i] = w[ids[i]];
        vector<int> sum(n + 1, 0);
        rep(i, n) {
            sum[i + 1] = sum[i] + a[i];
        }
        vector<vector<int>> dist(n + 1, vector<int>(n + 1, inf));
        rep(i, n) {
            for(int j = i + 1; j <= n; ++ j) {
                int sumv = sum[j] - sum[i];
                int k = lower_bound(all(vs), sumv) - vs.begin();
                // cerr << *lower_bound(all(vs), sumv) << endl;
                int le = lma[k];
                dist[i][j] = le;
                // cerr << i << " " << j << " " << sumv << " " << le << endl;
            }
        }
        vector<int> dp(n + 1, 0);
        dp[1] = 0;
        for(int i = 1; i < n; ++ i) {
            for(int j = i + 1; j <= n; ++ j) {
                chmax(dp[j], dp[i] + dist[i - 1][j]);
            }
        }
        chmin(ans, dp[n]);
    } while(next_permutation(all(ids)));
    if(ans >= inf) ans = -1;
    cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}