RT，#5本来错误代码过了的，后来改了一下从10到95但是原来对的却死活过不去……救救孩子吧

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 2505;
const int M = 1e4 + 5;
const int INF = 1e19;

int n, m, k;
int val[N];
int a[N][N];
int mx[N][4];

int head[N], cnt;
struct E {
	int nxt, to;
} e[M << 1];

void add(int u, int v) {
	e[++cnt].nxt = head[u];
	e[cnt].to = v;
	head[u] = cnt;
}

struct Node {
	int v, dis;
	bool operator < (const Node &y) const {
		return y.dis < dis;
	}
};
struct Now {
	int val, id;
} now[N];

bool cmp(Now x, Now y) {
	return x.val > y.val;
}

int dis[N], vis[N];

priority_queue<Node> q;

void prework(int x) {
	for (int i = 0; i <= n; i++) dis[i] = INF;
	memset(vis, 0, sizeof vis);
	while (!q.empty()) q.pop();
	dis[x] = 0; q.push((Node){x, 0});
	while (!q.empty()) {
		int u = q.top().v; q.pop();
		if (vis[u] || dis[u] > k) continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1;
				q.push((Node){v, dis[v]});
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (i == x) { a[x][i] = 1; continue; }
		if (dis[i] <= k) {
			a[x][i] = a[i][x] = 1;
		}
	}
	
	int len = 0;
	for (int i = 2; i <= n; i++) {
		if (a[x][i] && a[1][i]) now[++len].id = i, now[len].val = val[i];
	}
	sort(now + 1, now + 1 + len, cmp);
	for (int i = 1; i <= min(len, 3ll); i++) mx[x][i] = now[i].id;
}
signed main() {
//	freopen("holiday.in","r",stdin);
//	freopen("holiday.out","w",stdout);
	scanf("%lld %lld %lld", &n, &m, &k);k++;
	for (int i = 2; i <= n; i++) scanf("%lld", &val[i]);
	for (int i = 1; i <= m; i++) {
		int x, y; scanf("%lld %lld", &x, &y);
		add(x, y), add(y, x);
	}
	for (int i = 1; i <= n; i++) prework(i);
	
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= n; j++) printf("%d ", a[i][j]); puts("");
//	}
	
	long long ans = 0;
	int id1, id2, id3, id4;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j || !a[i][j]) continue;
			for (int p = 1; p <= 3; p++) {
				for (int q = 1; q <= 3; q++) {
					if (mx[i][p] != i && mx[i][p] != j && mx[i][p] != mx[j][q] && a[1][mx[i][p]] && a[mx[j][q]][1] && mx[j][q] != i && mx[j][q] != j) {
						ans = max(ans, 1ll * val[i] + val[j] + val[mx[i][p]] + val[mx[j][q]]);
					}
				}
			}
		}
	}
	printf("%lld\n", ans);
//	printf("%d %d %d %d\n", id1, id2, id3, id4);
	return 0;
}