#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+10;
vector<int> edge[N];
int ma[N][N];
int n,m,k;
int va[N];
int a,b;
int ans=0;
int sg[N];
void dfs1(int p,int u,int dep){
	if(dep==0)return;
	for(int v:edge[u]){
		if(!sg[v]){
			ma[p][v]=true;
			sg[v]=true;
			dfs1(p,v,dep-1);
		}
	}
}
int f[N];
void dfs2(int u,int res,int dep){
	if(dep==0){
		f[u]=max(res,f[u]);
		return;
	}
	for(int v=1;v<=n;v++){
		if(!sg[v]&&ma[u][v]){
			sg[v]=true;
			dfs2(v,res+va[v],dep-1);
			sg[v]=false;
		}
	}
}
void dfs3(int u,int res,int dep){
	if(dep==3)
		if(res+f[u]<ans)
			return;
	if(dep==1){
		if(ma[1][u])ans=max(ans,res);
		return;
	}
	for(int v=1;v<=n;v++){
		if(!sg[v]&&ma[u][v]){
			sg[v]=true;
			dfs3(v,res+va[v],dep-1);
			sg[v]=false;
		}
	}
}
signed main(){
	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=2;i<=n;i++)scanf("%lld",&va[i]);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&a,&b);
		edge[a].push_back(b),edge[b].push_back(a);
	}
	for(int i=1;i<=n;i++)ma[i][i]=1;
	for(int i=1;i<=n;i++){
		memset(sg,0,sizeof sg);
		sg[i]=true;
		dfs1(i,i,k+1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<ma[i][j]<<" ";
		}
		puts("");
	}
	memset(sg,0,sizeof sg);
	sg[1]=true;
	dfs2(1,0ll,2);
//	for(int i=1;i<=n;i++)
//		cout<<f[i]<<" ";
//	puts("");
	memset(sg,0,sizeof sg);
	sg[1]=true;
	dfs3(1,0ll,5);
	cout<<ans;
	return 0;
}

dfs1建图，邻接矩阵，dfs2预处理估值函数，估值函数f[x]表示从1走到x走两步最多拿多少分，dfs3就是暴力找，当找到第三步的时候调用估值函数看看要不要继续搜索。官方90，冥间总共WA5个，求调