蒟蒻求助WA on Sub0 #31, Sub1 #1, #5, Sub2 #21, #21，然而有十五个点MLE了，我算过空间不应该超限啊

#include<queue>
#include<vector>
#include<iostream>
using namespace std;

#define N 2505
long long ans,score[N];
int n,m,k,a,b,dist[N][N];

vector<int> adj[N];
struct node{
    int first;
    long long second;
}Max[N][3];
queue<node>q;

void bfs(int st){
	q.push(node{st,0});
	
	while(!q.empty()){
		int t=q.front().second,pts=q.front().first;
		q.pop();
		
		bool flag=0;
		if(!dist[1][pts]||pts==st) flag=1;
		if(score[pts]>Max[st][0].second&&!flag){
			Max[st][0].first=pts;
		    Max[st][0].second=score[pts];
			flag=1;
		}
		if(score[pts]>Max[st][1].second&&!flag){
			Max[st][1].first=pts;
		    Max[st][1].second=score[pts];
			flag=1;
		}
		if(score[pts]>Max[st][2].second&&!flag){
			Max[st][2].first=pts;
		    Max[st][2].second=score[pts];
	    }
	    if(st!=pts) dist[st][pts]=1;
	    if(t==k+1) continue;
		for(int i=0;i<adj[pts].size();i++) q.push(node{adj[pts][i],t+1});
	}
}
signed main(){
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++) cin>>score[i];
	
	for(int i=1;i<=m;i++){
	    cin>>a>>b;
		adj[a].push_back(b),adj[b].push_back(a);
	}
	for(int i=1;i<=n;i++) bfs(i);
	
	for(int i=2;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if(!dist[i][j]) continue;
			
			for(int x=0;x<3;x++){
				for(int y=0;y<3;y++){
					int a1=Max[i][x].first,a2=Max[j][y].first;
					if(a1!=j && a2!=i && a1!=a2 && a1!=0 && a2!=0){
						ans=max(ans,score[i]+score[j]+Max[i][x].second+Max[j][y].second);
					}
				}
			}
        }
	}
	cout<<ans;
	return 0;
}