题目描述

小熊的地图上有 $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 → 家这段行程转车时经过的点。 假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

输入

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

输出

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

输入样例

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 解释】 当计划的行程为 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 ≤ 2500$, $1 ≤ m ≤ 10000$, $0 ≤ k ≤ 100$, 所有景点的分数$1 ≤ s_i ≤ 10^{18}$。保证至少存在一组符合要求的行程。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。