Bear's map has $n$ points, where point 1 is his home, and points $2, 3, \dots, n$ are tourist attractions. Some pairs of points are connected by bidirectional direct bus routes. If there are direct routes between $x$ and $z_1$, $z_1$ and $z_2$, $\dots$, $z_{k-1}$ and $z_k$, and $z_k$ and $y$, we say that the journey between $x$ and $y$ can be completed with $k$ transfers. Specifically, if there is a direct route between $x$ and $y$, it is said to be completed with 0 transfers.

The holidays are coming soon, and Bear plans to leave home to visit 4 different attractions, completing a 5-leg journey before returning home: Home $\to$ Attraction A $\to$ Attraction B $\to$ Attraction C $\to$ Attraction D $\to$ Home, with each leg having at most $k$ transfers. There are no restrictions on the points passed through during transfers; they can be the home, an attraction, or the same point can be visited multiple times. For example, in the leg Attraction A $\to$ Attraction B, the points passed through during transfers can be the home, another attraction C, or even points passed through during the Attraction D $\to$ Home leg.

Assuming each attraction has a score, please help Bear plan a route such that the sum of the scores of the four different attractions visited is maximized.

Input

The input is read from the file holiday.in.

The first line contains 3 positive integers $n, m, k$, representing the number of points on the map, the number of pairs of points with direct bidirectional routes, and the maximum number of transfers for each leg, respectively.

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

The next $m$ lines each contain two positive integers $x, y$, representing that there is a direct road between point $x$ and $y$. It is guaranteed that $1 \le x, y \le n$, there are no multiple edges, and no self-loops.

Output

The output is written to the file holiday.out.

Output a single positive integer representing the maximum sum of the scores of the 4 different attractions Bear visits.

Examples

Input 1

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

Output 1

27

Note 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 attractions is $9+7+8+3 = 27$, which can be proven to be the maximum.

The sum of attraction scores for the route $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 meet the requirements, but the sum of scores is not the maximum.

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

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

Input 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

Output 2

7

Examples 3

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

Constraints

For all data, it is guaranteed that $5 \le n \le 2500$, $1 \le m \le 10000$, $0 \le k \le 100$, and all attraction scores $1 \le s_i \le 10^{18}$. It is guaranteed that at least one valid route exists.