Connected Subgraph Maximum Value

You are given an undirected graph with n vertices and m edges. Each vertex i has an associated integer value. Your task is to find a connected subgraph containing exactly k vertices such that the sum of the values of these vertices is maximized.

A subgraph is said to be connected if, for every pair of vertices in the subgraph, there exists a path between them using only the vertices within the subgraph.

If no such connected subgraph exists, your program should output -1.

Mathematically, if S is a subset of vertices with |S| = k, you are to maximize:

[ \sum_{i \in S} v_i ]

subject to the condition that the subgraph induced by S is connected.

Note: The vertex indices are zero-indexed.

inputFormat

The input is given via stdin and has the following format:

n m k
v0 v1 ... vn-1
u1 v1
...
m vm

Where:

• n is the number of vertices.
• m is the number of edges.
• k is the number of vertices to select for the connected subgraph.
• The second line contains n integers representing the value of each vertex.
• Each of the following m lines contains two integers u and v indicating there is an undirected edge between vertex u and vertex v.

outputFormat

The output should be printed to stdout and is a single integer:

• The maximum possible sum of vertex values for a connected subgraph with exactly k vertices.
• If no such subgraph exists, output -1.

## sample

5 4 3
1 2 3 4 5
0 1
0 2
0 3
3 4

10