小熊的地图上有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，且没有重边，自环。
输入样例1：
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
输入样例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输出样例1：
27
输出样例2：
7
当计划的行程为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≤si≤10^18。
保证至少存在一组符合要求的行程。
