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

typedef vector<int> vi;  
typedef pair<int,int> ii;  
typedef vector<ii> vii;  
typedef list<int> li;  
typedef set<int> si;
typedef stack<int> sti;
typedef map<int,int> mii;
  
#define rep(i,n) for (int i = 0; i < (n); i++)  
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)  

//vals: the array which will be used for median calculation
vector<vi> adj,adj2,in,in2,vals;
//val: the initial value the node has
//val2: the value of the component-node in dag
vi p,r,s,emp,l,newmap,val2,val,oldmap;  //newmap: the mapping from scc id in original graph to node id in the dag
int nmid = 0; 
vector<vi> arr; //the array that will include the sorted budget values

vector<bool> vis,istarget;
vector<si> compo; //compo: which components are already connected to others
si empo;
sti sta;

void dsu(int size) {  
    p.resize(size);  
    r.resize(size);  
    s.resize(size);  
    rep(i,size) {  
        p[i] = i;  
        r[i] = s[i] = 1;  
    }  
}  
  
int dsu_find(int v) { return (p[v]==v) ? v : (p[v] = dsu_find(p[v])); }  
  
void dsu_union(int root1, int root2) {  
    if (root1==root2) return;  
    if (r[root2] > r[root1]) {p[root1] = root2; return;}  
    r[root1]++;  
    p[root2] = root1;  
    s[root1]+=s[root2];  
}  
  
inline void visit(int v) {  
    if (vis[v]) return;  
    vis[v] = true;  
    rep(i, int(adj[v].size())) visit(adj[v][i]);  
    l.push_back(v); return;  
}  
  
inline void as(int u, int v) {  
    if (vis[u]) return;  
    vis[u] = true;  
    dsu_union(dsu_find(v), dsu_find(u));  
    rep(i,(int)(in[u].size())) as(in[u][i],v); return;  
} 

vi dist,topo;

vector<vector<long long int>> dp, dp_help;

inline void tsutil(int i) {
    vis[i] = true;
    rep(j,(int)adj2[i].size()) if (!vis[adj2[i][j]]) tsutil(adj2[i][j]);
    topo.push_back(i);
}
  
int main() 
{ 
    ios_base::sync_with_stdio(false);
    int T,N,M,u1,u2,K;
    long long int ovmax=0;
    //FILE *fpr = fopen("16.in","r");
    //FILE *fpo = fopen("16.out","w+");
    //fscanf(fpr,"%d",&T);
    cin >> T;
    rep(t,T) {
        ovmax=0;
        //fscanf(fpr, "%d %d %d",&N,&M,&K);
        cin >> N >> M >> K;
        
        dsu(N);
        l.clear();
        adj.assign(N,emp);
        val.resize(N);
        vals.assign(N,emp);
        in.assign(N,emp);
        vis.assign(N,false);
        newmap.assign(N,-1);
        oldmap.assign(N,-1);

        rep(i,N) {
            //fscanf(fpr, "%d", &val[i]);
            cin >> val[i];
        }

        rep(i,M) {
            //fscanf(fpr, "%d %d", &u1, &u2);
            cin >> u1 >> u2;
            u1--; u2--;
            //rep(j,(int)adj[u1].size()) { if (u2 == adj[u1][j]) cout << u1 << " " << u2 << endl;
            //}
            adj[u1].push_back(u2);
            in[u2].push_back(u1);
        }

       //create strongly connected components (kosaraju's)
        rep(i,N) visit(i);
        vis.assign(N,false);
        rrep(i,N) as(l[i],l[i]);
        vis.assign(N,false);

        //rep(i,N) cout << i << " " << p[i] << endl;

        //prepare to turn the scc's to dag
        nmid = 0;
        rep(i,N) if (newmap[p[i]]==-1) { newmap[p[i]]=nmid++; oldmap[nmid-1] = p[i]; }

        //make the new adjacency list
        adj2.assign(nmid,emp);
        in2.assign(nmid,emp);
        compo.assign(nmid,empo);
        rep(i,N) rep(j,(int)adj[i].size()) {
            if (newmap[p[i]] == newmap[p[adj[i][j]]]) continue;
            if (!(compo[newmap[p[i]]].find(newmap[p[adj[i][j]]]) != compo[newmap[p[i]]].end())) {
                adj2[newmap[p[i]]].push_back(newmap[p[adj[i][j]]]);
                in2[newmap[p[adj[i][j]]]].push_back(newmap[p[i]]);
            }
        }

        //sort the vectors that include the budgets
        arr.assign(nmid,emp);
        rep(i,N) arr[newmap[p[i]]].push_back(val[i]);
        rep(i,nmid) sort(arr[i].begin(),arr[i].end());
        rep(i,nmid) for (int j = arr[i].size(); j < K ; j++) arr[i].push_back(0);

        //cout << arr[0].size() << endl;

        //do the topological sorting
        topo = emp; //the array of topological sorting
        vis.assign(nmid,false);
        rep(i,nmid) if (!vis[i]) tsutil(i);
        
        //do the first dp 
        dp_help.resize(nmid);
        dp.resize(nmid);
        rep(i,nmid) {
            //cout << "i = " << i << endl;
            dp_help[i].assign(K+1,0);
            dp[i].assign(K+1,0);
        }
        //cout << dp_help[1][K] << endl;
        rrep(i,(int)topo.size()) {
            arr[topo[i]].push_back(1e9);
            //cout << topo[i] << endl;
            //do the first dp
                //cout << arr[topo[i]][0] << " " << s[oldmap[topo[i]]] << endl;
            rep(p,K+1) {
                rep(q,min(p,s[oldmap[topo[i]]])+1) {
                    if (p>(int)arr[topo[i]].size()) {break;}
                    dp[topo[i]][p] = max(dp[topo[i]][p],dp_help[topo[i]][p-q]+(long long int)arr[topo[i]][q]*(s[oldmap[topo[i]]]-q));
                    if (dp[topo[i]][p] > ovmax) ovmax = dp[topo[i]][p];
                }
                
                //cout << topo[i] << " " << p << " " << dp[topo[i]][p] << endl;
                //if (topo[i]==0 && p==1) cout << "blah" << endl;
            }

            //do the second dp
            rep(j,(int)adj2[topo[i]].size()) rep(p,K+1) dp_help[adj2[topo[i]][j]][p] = max(dp_help[adj2[topo[i]][j]][p], dp[topo[i]][p]);
                //cout << "value now is " << dp[topo[i]][p] << endl;
            
            /*
            for(int p=1;p<K+1;p++) {
                if (dp[topo[i]][p] < dp[topo[i]][p-1]) dp[topo[i]][p] = dp[topo[i]][p-1];
            }
            */
        }
        
        ovmax = ovmax % 1000000021;
        //fprintf(fpo, "%I64d\n", ovmax);
        cout << ovmax << endl;
    }
    return 0; 
    //compile: g++ -std=c++14 -O2 -Wall NAME.cpp -o NAME
}