小熊的地图上有 个点，其中编号为 的是它的家、编号为 的都是景点。部分点对之间有双向直达的公交线路。如果点 与 、 与 、……、 与 、 与 之间均有直达的线路，那么我们称 与 之间的行程可转车 次通达；特别地，如果点 与 之间有直达的线路，则称可转车 次通达。
很快就要放假了，小熊计划从家出发去 个不同的景点游玩，完成 段行程后回家：家 景点 A 景点 B 景点 C 景点 D 家且每段行程最多转车 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D 家这段行程转车时经过的点。
假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。
第一行包含三个正整数 ，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。
第二行包含 个正整数，分别表示编号为 的景点的分数。
接下来 行，每行包含两个正整数 ，表示点 和 之间有道路直接相连，保证 ，且没有重边，自环。
输出一个正整数，表示小熊经过的 个不同景点的分数之和的最大值。
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
【样例解释 #1】
当计划的行程为 时， 个景点的分数之和为 ，可以证明其为最大值。
行程 的景点分数之和为 、行程 的景点分数之和为 。它们都符合要求，但分数之和不是最大的。
行程 的景点分数之和为 ，但其中 至少需要转车 次，因此不符合最多转车 次的要求。
行程 的景点分数之和为 ，但游玩的并非 个不同的景点，因此也不符合要求。
【数据范围】
对于所有数据，保证 ，，，所有景点的分数 。保证至少存在一组符合要求的行程。
