假期计划

小熊的地图上有 n 个点，其中编号为 1 的是它的家、编号为2,3,…,n 的都是景点。部分点对之间有双向直达的公交线路。如果点 x 与 z_1、z_1与z_2、......、z_{k-1}与z_k、z_k与y均有直达的线路，那么我们称x与y之间的行程可转车k次通达；特别地，如果点 x 与 y 之间有直达的线路，则称可转车 0 次通达。 很快就要放假了，小熊计划从家出发去 4 个不同的景点游玩，完成 5 段行程后回家：家 → 景点 A → 景点 B → 景点 C → 景点 D → 家且每段行程最多转车 k 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A→ 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D → 家这段行程转车时经过的点。 假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

第一行包含三个正整数 n,m,k，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。 第二行包含 n−1 个正整数，分别表示编号为 2,3,…,n 的景点的分数。 接下来 m 行，每行包含两个正整数 x,y，表示点 x 和 y 之间有道路直接相连，保证 1≤x,y≤n，且没有重边，自环。

输出一个正整数，表示小熊经过的 4 个不同景点的分数之和的最大值。

【样例解释 #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 个不同的景点，因此也不符合要求。
【数据范围】
对于所有数据，保证 5≤n≤2500，1≤m≤10000，0≤k≤100，所有景点的分数 1≤s_i≤10^{8} 。保证至少存在一组符合要求的行程。

CSP