#include<bits/stdc++.h> 
using namespace std;
typedef unsigned long long LL;
typedef pair<LL,int> pii;
const int N=5000,M=10010;
const LL inf=1e18+10;
int n,m,k,num,vis[N];
int cnt,to[M<<1],nxt[M<<1],head[N];
LL a[N],f[N][10],dis[N][N];
pii p[N];
void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}
LL MAX(LL a,LL b){return (a>b?a:b);}
int MIN(int a,int b){return (a>b?b:a);}
bool cmp(pii x,pii y){return x.first>y.first;}
void bfs(int xx){
	num=0;
//	memset(p,0,sizeof(p));
	memset(vis,0,sizeof(vis));
	queue<pii> q;q.push(make_pair(xx,-1));
	while(!q.empty()){
		pii h=q.front();
		q.pop();
		int x=h.first;
		dis[xx][x]=h.second;
		if(x!=1&&x!=xx&&h.second<=k&&dis[1][x]<=k){
			p[++num]=make_pair(a[x],x);
			sort(p+1,p+1+num,cmp);
			if(num>3) num--;
//			cout<<"bfs::"<<x<<' '<<xx<<endl;
		}
		if(h.second==k) continue;
		vis[x]=1;
		for(int i=head[x];i!=0;i=nxt[i]){
			int y=to[i];
//			cout<<x<<' '<<y<<endl;
			if(vis[y])continue;
			q.push(make_pair(y,h.second+1));
		}
	}
	for(int j=1;j<=min(3,num);j++) f[xx][j]=p[j].second;//,cout<<xx<<' '<<p[j].second<<endl;
//	cout<<f[3][5]<<endl;
}

signed main(){
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0); 
  	freopen("nzq.in","r",stdin);
  	freopen("nzq.out","w",stdout);
	cin>>n>>m>>k;
 	for(int i=1;i<=n;i++){
	 for(int j=1;j<=n;j++) dis[i][j]=inf;}
	for(int i=2;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	bfs(1);
	memset(f,0,sizeof(f));
	for(int i=2;i<=n;i++){
		bfs(i);
	}
	LL Max=0;
	a[0]=-inf;
	for(int i=2;i<=n;i++){
		for(int j=2;j<=n;j++){
//			cout<<i<<' '<<j<<' '<<dis[1][i]<<' '<<dis[1][j]<<' '<<endl;
			if(i!=j&&dis[i][j]<=k)
			for(int s=1;s<=3;s++){
				for(int t=1;t<=3;t++){
					int x=f[i][s],y=f[j][t];
					if(x!=y&&x!=j&&y!=i&&x!=0&&y!=0)
					Max=MAX(Max,a[i]+a[j]+a[x]+a[y]);
//					cout<<dis[i][x]<<' '<<i<<' '<<j<<' '<<x<<' '<<y<<' '<<a[i]+a[j]+a[x]+a[y]<<endl;
				}	
			}
		}
	}
	cout<<Max<<endl;
//	cout<<dis[5][6]<<' '<<k<<endl;
//	cout<<f[3][5]<<endl;
    return 0;
}

思路与第一篇题解类似