Problem Description

There are $n$ points on Little Bear’s map. Point $1$ is its home, and points $2, 3, \ldots, n$ are all scenic spots. Between some pairs of points, there are bidirectional direct bus lines. If there are direct lines between $x$ and $z_1$, between $z_1$ and $z_2$, $\ldots$, between $z_{k - 1}$ and $z_k$, and between $z_k$ and $y$, then we say that the trip from $x$ to $y$ can be completed with $k$ transfers. In particular, if there is a direct line between $x$ and $y$, then it can be completed with $0$ transfers.

The holiday is coming soon. Little Bear plans to start from home and visit $4$ different scenic spots, then return home after completing $5$ segments of travel: home $\to$ spot A $\to$ spot B $\to$ spot C $\to$ spot D $\to$ home. Each segment may use at most $k$ transfers. There are no restrictions on the points passed during transfers: they can be home, scenic spots, and the same point may be passed multiple times. For example, in the segment from spot A $\to$ spot B, the points passed during transfers can include home, or spot C, and they may even include points that are passed during transfers in the segment spot D $\to$ home.

Assume each scenic spot has a score. Please help Little Bear plan a route so that the sum of the scores of the four different scenic spots it visits is maximized.

Input Format

The first line contains three integers $n, m, k$, representing the number of points on the map, the number of bidirectional directly connected pairs, and the maximum number of transfers allowed for each segment.

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

The next $m$ lines each contain two positive integers $x, y$, indicating that points $x$ and $y$ are directly connected by a road. It is guaranteed that $1 \le x, y \le n$, and there are no multiple edges or self-loops.

Output Format

Output one positive integer, the maximum possible sum of the scores of the $4$ different scenic spots that Little Bear visits.

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

Hint

[Sample Explanation #1]

When the planned route 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$. It can be proven that this is the maximum.

The sum of scenic spot scores for the route $1 \to 3 \to 5 \to 7 \to 8 \to 1$ is $24$, and for the route $1 \to 3 \to 2 \to 8 \to 7 \to 1$ is $25$. They both meet the requirements, but their sums are not the maximum.

The sum of scenic spot scores for the route $1 \to 2 \to 3 \to 5 \to 8 \to 1$ is $30$, but in it, $5 \to 8$ requires at least $2$ transfers, so it does not satisfy the requirement of at most $k = 1$ transfer.

The sum of scenic spot scores for the route $1 \to 2 \to 3 \to 2 \to 3 \to 1$ is $32$, but the trip does not visit $4$ different scenic spots, so it also does not meet the requirements.

[Sample #3]

See holiday/holiday3.in and holiday/holiday3.ans in the attachment.

[Constraints]

For all testdata, it is guaranteed that $5 \le n \le 2500$, $1 \le m \le 10000$, $0 \le k \le 100$, and for all scenic spots, $1 \le s_i \le {10}^{18}$. It is guaranteed that there exists at least one route that meets the requirements.

Translated by ChatGPT 5