Person in Charge

• SleepingCup

Problem Description

There are $n$ points on Little Bear's map, where point numbered $1$ is its home and points numbered $2, 3, \ldots, n$ are all scenic spots. There are bidirectional direct bus routes between some pairs of points. If there are direct routes between point $x$ and $z_1$, $z_1$ and $z_2$, $\ldots$, $z_{k-1}$ and $z_k$, $z_k$ and $y$, then we say that $x$ and $y$ are reachable with exactly $k$ transfers. In particular, if there is a direct route between $x$ and $y$, they are reachable with $0$ transfers.

The holiday is coming soon. Little Bear plans to start from home and visit $4$ distinct scenic spots, completing $5$ trips and then returning home, following the route: $\text{Home} \to \text{Scenic Spot A} \to \text{Scenic Spot B} \to \text{Scenic Spot C} \to \text{Scenic Spot D} \to \text{Home}$. Each trip is allowed to have at most $k$ transfers. There are no restrictions on the points passed during transfers — they can be the home, scenic spots, or even points that are repeatedly traversed. For example, during the trip from Scenic Spot A to Scenic Spot B, the points passed during transfers can be the home, Scenic Spot C, or even the points passed during the transfer of the trip from Scenic Spot D to home.

Each scenic spot has a score. Please help Little Bear plan the trip such that the sum of the scores of the $4$ distinct scenic spots visited is maximized.

Input Format

The first line contains three positive integers $n, m, k$, representing the number of points on the map, the number of pairs of points connected by direct bidirectional routes, and the maximum number of transfers allowed for each trip respectively.

The second line contains $n-1$ positive integers, denoting the scores of the scenic spots numbered $2, 3, \ldots, n$ in order.

The next $m$ lines each contain two positive integers $x, y$, indicating that there is a direct bidirectional route between point $x$ and point $y$. It is guaranteed that $1 \le x, y \le n$, with no duplicate edges or self-loops.

Output Format

Output a positive integer, representing the maximum sum of the scores of the $4$ distinct scenic spots that Little Bear visits in a valid trip.

Samples

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

Sample (1) Explanation

When the planned trip is $1 \to 2 \to 3 \to 5 \to 7 \to 1$, the sum of the scores of the 4 scenic spots is $9 + 7 + 8 + 3 = 27$, which is proven to be the maximum possible value.

The sum of scores for the trip $1 \to 3 \to 5 \to 7 \to 8 \to 1$ is $24$, and for $1 \to 3 \to 2 \to 8 \to 7 \to 1$ is $25$. Both trips satisfy the requirements but yield a smaller sum of scores.

The sum of scores for the trip $1 \to 2 \to 3 \to 5 \to 8 \to 1$ is $30$, yet the trip from $5$ to $8$ requires at least $2$ transfers, which violates the constraint of at most $k=1$ transfer.

The sum of scores for the trip $1 \to 2 \to 3 \to 2 \to 3 \to 1$ is $32$, but it does not visit $4$ distinct scenic spots and thus fails to meet the requirement.

Sample (3)

See holiday/holiday3.in and holiday/holiday3.ans in the contestant's directory.

Data Range

For all test data, it is guaranteed that $5 \le n \le 2500$, $1 \le m \le 10000$, $0 \le k \le 100$, and the score of each scenic spot satisfies $1 \le s_i \le 10^{18}$. It is guaranteed that there exists at least one valid trip.