RT

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2505;
const int MAXM=2e5+5;
struct node
{
	int to,nxt;
}e[MAXM];
int head[MAXM],cnt;
inline void add(int x,int y)
{
	e[++cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
int n,m,k;
int val[MAXN];
bitset<MAXN>vis;
int dis[MAXN];
bool ct[MAXN][MAXN];
int dp[MAXN][5];
int path[MAXN][5][5];//记录x的路径 
vector<pair<int,int> >v1,v2;
signed main()
{
//	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);	
	scanf("%lld%lld%lld",&n,&m,&k);
	for(register int i=2;i<=n;i++)
		scanf("%lld",&val[i]);
	for(register int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(register int i=1;i<=n;i++)
	{
		memset(dis,0x3f,sizeof dis);
		queue<int>q;
		q.push(i);
		dis[i]=-1;
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			vis[x]=0;
			for(register int j=head[x];j;j=e[j].nxt)
			{
				int y=e[j].to;
				if(dis[y]>dis[x]+1)
				{
					dis[y]=dis[x]+1;
					if(!vis[y])
					{
						vis[y]=1;
						q.push(y);
					}
				}
			}
		}
		for(register int j=1;j<=n;j++)
			if(dis[j]<=k)ct[i][j]=1;
	}
	for(register int tim=1;tim<=4;tim++)
		for(register int i=1;i<=n;i++)
			for(register int j=2;j<=n;j++)
			{
				bool flag=false;
				if((i==j)||(!ct[i][j]))continue;
				if(tim==1&&(!ct[1][j]))continue;
				if(tim==4&&(!ct[1][j]))continue;
				for(register int l=1;l<=4;l++)
					if(j==path[i][tim-1][l])flag=true;
				if(flag)continue;
				if(dp[j][tim]<dp[i][tim-1]+val[j])
				{
					dp[j][tim]=dp[i][tim-1]+val[j];
					for(register int l=1;l<=4;l++)
						path[j][tim][l]=path[i][tim-1][l];
					path[j][tim][tim]=j;
				}
			}
	int maxn=0;
	for(register int i=1;i<=n;i++)
	{
		bool skip=false;
		for(register int k=1;k<=4;k++)
		{
//			printf("%d ",path[i][4][k]);
			if(!path[i][4][k])skip=true;
		}
//		printf("%d",dp[i][4]);
//		puts("");
		if(skip)continue;
		maxn=max(maxn,dp[i][4]);
	}
	printf("%lld",maxn);
	return 0;
}

民间数据甚至90分