记录

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

int s[2505],dis[2505][2505],ans,n,m,k,f[2505][6];
vector<int> g[2505],e[2505];
bool flag[2505];

void bffa(int x){
	memset(dis[x],63,20008);
	queue<int> q;
	q.push(x);
	dis[x][x] = 0;
	flag[x] = true;
	while(!q.empty()){
		int u = q.front(),v;
		q.pop();
		flag[u] = false;
		for(int i = 0;i < g[u].size();i++){
			v = g[u][i];
			if(dis[x][v]>dis[x][u]+1){
				dis[x][v] = dis[x][u]+1;
				if(!flag[v]) q.push(v); 
			}
		}
	}
}

void dfs(int x,int num,int sum){
	if(num==5){
		if(dis[x][1]<=k+1) ans = max(ans,sum);
		return;
	}
	if(sum<f[x][num]) return;
	f[x][num] = sum;
	for(int i = 0;i < e[x].size();i++){
		if(flag[e[x][i]]||e[x][i]==1) continue;
		flag[e[x][i]] = 1;
		dfs(e[x][i],num+1,sum+s[e[x][i]]);
		flag[e[x][i]] = 0;
	}
}

signed main()
{
	cin >> n >> m >> k;
	for(int i = 2;i <= n;i++){
		cin >> s[i];
	}
	int x,y;
	for(int i = 1;i <= m;i++){
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i = 1;i <= n;i++){
		bffa(i);
	}
	for(int i = 1;i <= n;i++){
		for(int j = i+1;j <= n;j++){
			if(dis[i][j]<=k+1){
				e[i].push_back(j);
				e[j].push_back(i);
			}
		}
	}
	dfs(1,1,0);
	cout << ans << endl;
	return 0;
}