关于我被#24hack这件事……

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,val[3305],a,b,k,mp[3305][3305];
int dis[3305][7];
vector<int> v[3500];
int vis[3500];
struct node{
	int now,num,cnt;
	set<int> st;
};
struct node2{
	int u,step;
};

void bfs(int sx)
{
	for(int i=0;i<=n;i++)vis[i]=0;
	queue<node2> q;
	q.push({sx,0});
	vis[sx]=1;
	while(!q.empty())
	{
		node2 f=q.front();q.pop();
		mp[sx][f.u]=mp[f.u][sx]=min(mp[sx][f.u],f.step);
		for(auto go:v[f.u]) if(!vis[go]) vis[go]=1,q.push({go,f.step+1});
	}
}

void floyed()
{
	for(int i=1;i<=n;i++)bfs(i);
}

signed main()
{
//	freopen("P8817_24.in","r",stdin);
//	freopen("P8817.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++)cin>>val[i];
	for(int i=0;i<=3300;i++)
		for(int j=0;j<=3300;j++)
			mp[i][j]=1e18;
	for(int i=1;i<=n;i++)mp[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		mp[a][b]=mp[b][a]=1;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=0;i<=n+5;i++)
		for(int j=0;j<=6;j++)
			dis[i][j]=1e18;
	floyed();
	queue<node> q;
	node tmp;
	tmp.now=1;
	tmp.num=0;
	tmp.cnt=0;
	tmp.st.insert(1);
	q.push(tmp);
	while(!q.empty())
	{
		node f=q.front();q.pop();
		if(f.cnt>=4)continue;
		for(int go=2;go<=n;go++)
		{
			if(go==f.now)continue;
			if(mp[f.now][go]-1<=k&&dis[go][f.cnt+1]<=f.num+val[go]&&f.st.find(go)==f.st.end())
			{
				dis[go][f.cnt+1]=f.num+val[go];
				node t;
				t.now=go;
				t.num=f.num+val[go];
				t.cnt=f.cnt+1;
				t.st=f.st;
				t.st.insert(go);
				q.push(t);
			}
		}
	}
	int ans=-1;
	for(int i=0;i<=n;i++) if(mp[i][1]-1<=k) ans=max(ans,dis[i][4]);
	cout<<ans<<endl;
	return 0;
}