Maximum Attraction Score Trip

Little Bear has a map with (n) nodes, where node (1) is his home and nodes (2, 3, \ldots, n) are attractions. There are bidirectional bus routes connecting some pairs of nodes. For two nodes (x) and (y), if there exists a sequence of nodes (z_1, z_2, \ldots, z_k) such that there is a direct bus 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 (x) and (y) are accessible with (k) transfers. In particular, if there is a direct route between (x) and (y), then they are accessible with (0) transfers.

Little Bear plans to visit 4 different attractions by taking a journey with 5 segments:
[ \text{home} \to A \to B \to C \to D \to \text{home} ]
such that each segment is accessible with at most (k) transfers. Note that if a segment has a shortest path with (d) edges then it requires (d-1) transfers. Hence the constraint for a segment is
[ \text{distance} \leq k+1 ]
.
Each attraction (node (2,3,\ldots,n)) has an associated score. Your task is to choose 4 distinct attractions (A, B, C, D) and plan the trip so that all 5 segments
(1\to A,\ A\to B,\ B\to C,\ C\to D, \ D\to 1) satisfy the accessibility condition and the total score of the visited attractions is maximized. If no valid journey exists, output -1.

inputFormat

The input consists of multiple lines.
The first line contains three integers (n), (m), (k) where (n) is the number of nodes, (m) is the number of bus routes, and (k) is the maximum allowed number of transfers for each segment (note that a route with (d) edges has (d-1) transfers and must satisfy (d \leq k+1)).
The second line contains (n-1) integers, representing the scores of the attractions at nodes (2,3,\ldots,n) respectively.
Each of the next (m) lines contains two integers (u) and (v) indicating there is a bidirectional bus route between nodes (u) and (v).

outputFormat

Output a single integer: the maximum total score of the 4 attractions on a valid journey. If no such journey exists, output -1.

sample

5 5 1
10 20 30 40
1 2
2 3
3 4
4 5
5 1

100