题目描述

小猴住在一片群岛上,它的地图上有 $n$ 个地点:编号为 $1$ 的是它居住的小岛,编号为 $2, 3, \ldots, n$ 的都是可游玩的小岛。部分地点之间开有双向直达的定期航线。若地点 $x$ 与 $z_1$、$z_1$ 与 $z_2$、……、$z_{k-1}$ 与 $z_k$、$z_k$ 与 $y$ 之间都有直达航线,则称从 $x$ 到 $y$ 的行程可中转 $k$ 次到达;特别地,若 $x$ 与 $y$ 之间有直达航线,则称可中转 $0$ 次到达。

假期将至,小猴打算从家出发游览 $4$ 个不同的小岛,走完 $5$ 段行程后回家:家 $\to$ 景点 A $\to$ 景点 B $\to$ 景点 C $\to$ 景点 D $\to$ 家,且每段行程的中转次数不超过 $k$。中转时经过的地点不受任何限制:可以是家、可以是景点,也可以与其它行程段经过的地点重复。例如在「景点 A $\to$ 景点 B」这段行程中,中转经过的地点可以是家,也可以是景点 C,还可以与「景点 D $\to$ 家」这段行程中转经过的地点相同。

每个景点都有一个分数,请帮小猴规划一个行程,使它游览的 $4$ 个不同景点的分数之和最大。

输入格式

输入第一行包含三个整数 $n, m, k$,分别表示地图上地点的个数、双向直达航线的条数、每段行程最多的中转次数。

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

接下来 $m$ 行,每行两个正整数 $x, y$,表示地点 $x$ 与 $y$ 之间有直达航线,保证 $1 \le x, y \le 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

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 解释】

当行程为 $1 \to 2 \to 3 \to 5 \to 7 \to 1$ 时,$4$ 个景点的分数之和为 $9 + 7 + 8 + 3 = 27$,可以证明这已是最大值。

行程 $1 \to 3 \to 5 \to 7 \to 8 \to 1$ 的分数之和为 $24$;行程 $1 \to 3 \to 2 \to 8 \to 7 \to 1$ 的分数之和为 $25$。它们都符合要求,但分数之和不是最大。

行程 $1 \to 2 \to 3 \to 5 \to 8 \to 1$ 的分数之和为 $30$,但其中 $5 \to 8$ 至少需要中转 $2$ 次,不满足最多中转 $k = 1$ 次的要求。

行程 $1 \to 2 \to 3 \to 2 \to 3 \to 1$ 的分数之和为 $32$,但游览的并非 $4$ 个不同的景点,同样不符合要求。

【数据范围】

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