rt，WA hack #5，#6

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> P;
const int N = 2505;
int n, m, k, dis[N], g[N][N];
P c[N][3];
ll ans, a[N];
queue<int> q;
vector<int> e[N];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 2; i <= n; i++)
		scanf("%lld", &a[i]);
	for (; m--; ) {
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		memset(dis, 127, sizeof(dis));
		dis[i] = 0;
		q.push(i);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (auto y : e[x])
				if (dis[y] > dis[x] + 1)
					dis[y] = dis[x] + 1, q.push(y);
		}
		for (int j = 1; j <= n; j++)
			if (dis[j] <= k + 1)
				g[i][j] = 1;
		g[i][i] = 0;
	}
	for (int i = 2; i <= n; i++) {
		P m1(0, 0), m2(0, 0), m3(0, 0);
		for (int j = 1; j <= n; j++)
			if (g[1][j] && g[i][j] && i != j) {
				P p(a[j], j);
				if (p > m1)
					m3 = m2, m2 = m1, m1 = p;
				else {
					if (p > m2)
						m3 = m2, m2 = p;
					else
						m3 = max(m3, p);
				}
			}
		c[i][0] = m1;
		c[i][1] = m2;
		c[i][2] = m3;
	}
	for (int u1 = 2; u1 <= n; u1++)
		for (int u2 = u1 + 1; u2 <= n; u2++)
			if (g[u1][u2])
				for (int p1 = 0; p1 < 3; p1++)
					for (int p2 = 0; p2 < 3; p2++) {
						int v1 = c[u1][p1].second, v2 = c[u2][p2].second;
						if (v1 && v2 && v1 != u2 && v2 != u1 && v1 != v2)
							ans = max(ans, a[u1] + a[u2] + a[v1] + a[v2]);
					}
	printf("%lld\n", ans);
}