题目描述

小熊的地图上有 $\red{n}$个点，其中编号为 $\red{1}$的是它的家、编号为 $\red{2,3,...,n}$的都是景点。部分点对之间有双向直达的公交线路。如果点 $\red{x}$ 与 $\red{z_1}$、$\red{z_1}$与 $\red{z_2}$、$\red{......}$、$\red{z_{k - 1}}$与$\red{z_k}$、$\red{z_k}$ 与 $\red{y}$ 之间均有直达的线路，那么我们称 $\red{x}$ 与 $\red{y}$ 之间的行程可转车 $\red{k}$次通达；特别地，如果点 $\red{x}$ 与 $\red{y}$ 之间有直达的线路，则称可转车 $\red{0}$ 次通达。

很快就要放假了，小熊计划从家出发去 $\red{4}$ 个不同的景点游玩，完成 $\red{5}$ 段行程后回家：家 $\red{→}$ 景点 A $\red{→}$ 景点 B $\red{→}$ 景点 C$\red{→}$ 景点 D $\red{→}$ 家且每段行程最多转车 $\red{k}$ 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A $\red{→}$ 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D $\red{→}$ 家这段行程转车时经过的点。

假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

输入格式

第一行包含三个正整数 $\red{n,m,k}$，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

第二行包含 $\red{n - 1}$个正整数，分别表示编号为 $\red{2, 3, \ldots, n}$ 的景点的分数。

接下来 $\red{m}$ 行，每行包含两个正整数 $\red{x , y}$*，表示点 $\red{x}$ 和 $\red{y}$ 之间有道路直接相连，保证$\red{1 \le x, y \le n}$，且没有重边，自环。

输出格式

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

样例

输入数据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

输出数据1

27

输入数据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

提示

【样例1解释】 当计划的行程为 $\red{1 \to 2 \to 3 \to 5 \to 7 \to 1}$ 时，4 个景点的分数之和为 $\red{9 + 7 + 8 + 3 = 27}$，可以证明其为最大值。

行程 $\red{1 \to 3 \to 5 \to 7 \to 8 \to 1}$ 的景点分数之和为 $\red{24}$、行程 $\red{1 \to 3 \to 2 \to 8 \to 7 \to 1}$ 的景点分数之和为 $\red{25}$。它们都符合要求，但分数之和不是最大的。

行程 $\red{1 \to 2 \to 3 \to 5 \to 8 \to 1}$ 的景点分数之和为 $\red{30}$，但其中 $\red{5 \to 8}$ 至少需要转车 $\red{2}$ 次，因此不符合最多转车 $\red{k = 1}$ 次的要求。

行程 $\red{1 \to 2 \to 3 \to 2 \to 3 \to 1}$ 的景点分数之和为 $\red{32}$，但游玩的并非 $\red{4}$ 个不同的景点，因此也不符合要求。

范围： 对于所有数据，保证 $\red{5 \le n \le 2500}$，$\red{1 \le m \le 10000}$，$\red{0 \le k \le 100}$，所有景点的分数 $\red{1 \le s_i \le {10}^{18}}$。保证至少存在一组符合要求的行程。