小熊的地图上有 n 个点，其中编号为 1 的是它的家、编号为 2,3,...,n 的都是景点。部分点对之间有双向直达的公交线路。如果点 x 与 z1、z1与 z2、……、zk−1 与 zk、zk 与 y 之间均有直达的线路，那么我们称 x 与 y 之间的行程可转车 k 次通达；特别地，如果点 x 与 y 之间有直达的线路，则称可转车 0 次通达。
很快就要放假了，小熊计划从家出发去 4 个不同的景点游玩，完成 5 段行程后回家：家 → 景点 A → 景点 B → 景点 C → 景点 D → 家且每段行程最多转车 k 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A → 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D → 家这段行程转车时经过的点。
假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。
第一行包含 3 个正整数 n,m, k，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。
第二行包含 n−1个正整数，分别表示编号为 2,3,...,n 的景点的分数。
接下来 m 行，每行包含两个正整数 x, y，表示点 x 和 y 之间有道路直接相连，保证 1≤x,y≤n，且没有重边，自环。
对于所有数据，保证 5≤n≤2500,1≤m≤10000,0≤k≤100，所有景点的分数 1≤si≤1018。
保证至少存在一组符合要求的行程。
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
当计划的行程为 1→2→3→5→7→1时，4 个景点的分数之和为 9+7+8+3=27，可以证明其为最大值。
行程 1→3→5→7→8→1的景点分数之和为 24、行程 1→3→2→8→7→1的景点分数之和为 25。
它们都符合要求，但分数之和不是最大的。
行程 1→2→3→5→8→1 的景点分数之和为 30，但其中 5→8至少需要转车 2 次，因此不符合最多转车 k=1次的要求。
行程 1→2→3→2→3→1的景点分数之和为 32，但游玩的并非 4 个不同的景点，因此也不符合要求。
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
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 127
【样例 1 解释】
当计划的行程为 1 → 2 → 3 → 5 → 7 → 1 时，4 个景点的分数之和为 9+7+8+3 = 27，可以证明其为最大值。
行程 1 → 3 → 5 → 7 → 8 → 1 的景点分数之和为 24、行程 1 → 3 → 2 → 8 → 7→ 1 的景点分数之和为 25。它们都符合要求，但分数之和不是最大的。
行程 1 → 2 → 3 → 5 → 8 → 1 的景点分数之和为 30，但其中 5 → 8 至少需要转车2 次，因此不符合最多转车 k = 1 次的要求。
行程 1 → 2 → 3 → 2 → 3 → 1 的景点分数之和为 32，但游玩的并非 4 个不同的景点，因此也不符合要求。
【样例 2 输入】
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
【样例 2 输出】
7
【数据范围】
对于所有数据，保证 5≤n≤25005≤�≤2500, 1≤m≤100001≤�≤10000, 0≤k≤1000≤�≤100, 所有景点的分数1≤si≤10181≤��≤1018。保证至少存在一组符合要求的行程。
| 测试点编号 | n ≤ | m ≤ | k ≤ |
| 1 ∼ 3 | 10 | 20 | 0 |
| 4 ∼ 5 | 5 | ||
| 6 ∼ 8 | 20 | 50 | 100 |
| 9 ∼ 11 | 300 | 1000 | 0 |
| 12 ∼ 14 | 100 | ||
| 15 ∼ 17 | 2500 | 10000 | 0 |
| 18 ∼ 20 | 100 |