Maximum Gold Collection in a Cave

You are given a cave consisting of N chambers connected by M bidirectional tunnels. Each chamber contains a certain amount of gold. Starting from chamber 0, your task is to visit exactly K distinct chambers following the tunnels and collect as much gold as possible.

The input consists of:

• N: the number of chambers.
• M: the number of tunnels.
• K: the exact number of chambers to visit.
• gold: an array where gold[i] is the amount of gold in the i-th chamber.
• tunnels: pairs of integers, each representing a bidirectional tunnel between two chambers.

Find and output the maximum total amount of gold that can be collected by visiting exactly K chambers, starting from chamber 0 and moving along the tunnels. If it is impossible to obtain a path of exactly K chambers, output the maximum obtainable gold from any valid configuration.

Note: All formulas used in this problem are in LaTeX. For example, the number of chambers is represented as \(N\), the number of tunnels as \(M\), and the sequence of visited chambers has exactly \(K\) elements.

inputFormat

The input is given from standard input (stdin) and has the following format:

(N) (M) (K) (gold_0) (gold_1) ... (gold_{N-1}) (u_1) (v_1) (u_2) (v_2) ... (u_M) (v_M)

where (N) is the number of chambers, (M) is the number of tunnels, (K) is the number of chambers to visit, the second line contains (N) integers representing the gold in each chamber, and the following (M) lines each describe a tunnel connecting two chambers.

outputFormat

Output a single integer to standard output (stdout) representing the maximum amount of gold that can be collected by visiting exactly (K) chambers.## sample

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

90