#include <bits/stdc++.h>
using namespace std;
const int N = 3e3+10;
const int Ne = 1e7+10;
typedef unsigned long long ull;
ull cnt, head[N], lll[N], pd[2600][2600], dist[2600][2600], temp[N][N], n, m, u, v, k, l1, l2, l3, h, t, q[N], q1[N], q2[N], q3[N], vis[N], q22[N], ans;
struct Node{
	ull to, next;
}g[Ne];
struct No{
	ull w0, w2, w3, w4;
	ull n21, n31, n32;
}a[N]; 
void add(ull x, ull y)
{
	g[++cnt].to = y;
	g[cnt].next = head[x];
	head[x] = cnt;
}

void bfs(int x)
{
	queue<int>q;
	q.push(x);
	memset(dist[x],0x3f,sizeof(dist[x]));
	dist[x][x]=0;
	for(;q.size();)
	{
		int u=q.front();q.pop();
		for(int i=head[u];i;i=g[i].next) 
			if(dist[x][g[i].to]>dist[x][u]+1)
			{
				dist[x][g[i].to]=dist[x][u]+1;
				q.push(g[i].to);
			}
	}
}
int main()
{
	cin >> n >> m >> k;
	k++;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) temp[i][j] = 110;
	for(int i=2;i<=n;i++) cin >> a[i].w0;
	for(int i=1;i<=m;i++)
	{
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}//1e4
	for(int i=1;i<=n;i++) bfs(i); 
	fill(head, head+n+1, 0);
	for(int i=0;i<=cnt;i++) g[i].to = g[i].next = 0; //1e3
	cnt = 0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		if(dist[i][j]<=k) pd[i][j] = 1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)//1e7
		{
			if(i==1&&pd[i][j]&&i!=j) q1[++l1] = j;
			if(pd[i][j]&&i!=j) add(i, j);
		}
	//q2代表存储第二位数的队列
	//q22代表该数是否是中间的数
	for(int i=1;i<=l1;i++)//1e3
		for(int j=head[q1[i]];j;j=g[j].next)//1e4
		{
			long long vv = g[j].to;
			if(vv==1) continue;
			if(!vis[vv]) vis[vv] = 1, q2[++l2] = vv, q22[vv] = 1;
			if(a[q1[i]].w0+a[vv].w0>a[vv].w2) a[vv].w2 = a[q1[i]].w0+a[vv].w0, a[vv].n21 = q1[i];
		}
	fill(vis, vis+n+1, 0);
	for(int i=1;i<=l2;i++)
		for(int j=head[q2[i]];j;j=g[j].next)
			{
				if(!vis[g[j].to]&&q22[g[j].to]&&g[j].to!=1) vis[g[j].to] = 1, q3[++l3] = g[j].to;
				if(q22[g[j].to]&&g[j].to!=1&&g[j].to!=a[q2[i]].n21&&a[g[j].to].w3<a[q2[i]].w2+a[g[j].to].w0) a[g[j].to].w3 = a[q2[i]].w2+a[g[j].to].w0, a[g[j].to].n31 = a[q2[i]].n21, a[g[j].to].n32 = q2[i];
			}
	
	fill(vis, vis+n+1, 0);
	for(int i=1;i<=l3;i++)
		for(int j=head[q3[i]];j;j=g[j].next)
			if(pd[g[j].to][1]&&g[j].to!=a[q3[i]].n31&&g[j].to!=a[q3[i]].n32&&ans<a[q3[i]].w3+a[g[j].to].w0) ans = a[a[q3[i]].n31].w0+a[a[q3[i]].n32].w0+a[q3[i]].w0+a[g[j].to].w0;
	cout << ans << endl;
	return 0;
}

Subtasks #2 全WA