题目描述

小熊从 $1$ 号点出发，依次游玩四个不同景点后回到 $1$ 号点。每段行程最多转车 $k$ 次，即图上距离不超过 $k+1$ 条边，求四个景点分数和的最大值。

输入格式

第一行三个正整数 $n,m,k$。

第二行 $n-1$ 个正整数，依次表示 $2\sim n$ 号景点的分数。

接下来 $m$ 行，每行两个正整数 $x,y$，表示一条无向边。

输出格式

输出一个正整数，表示最大分数和。

样例

8 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

27

7 9 0
1 1 1 2 3 4
1 2
2 3
3 4
1 5
1 6
1 7
5 4
6 4
7 4

7

来源

CSP-S 2022 T1

数据范围与提示

• $5 \le n \le 2500$
• $1 \le m \le 10000$
• $0 \le k \le 100$
• $1 \le s_i \le 10^{18}$
• 保证至少存在一组合法行程。