Problem B
Minimum Weighted Vertex Cover

The Minimum Weighted Vertex Cover (MWVC) problem is to find the vertex cover with the minimum sum of weights of a particular given graph.

Your program should take as input a single MWVC instance. It will be run several times, once for every test case. The time limit is per test case.

For simplicity, the graph will contain $N$ vertices and $E$ undirected edges. The vertices will be labelled from $0$ to $N-1$ and the graph will not contain multi-edges or self-loop.

Input

The first line of standard input contains two integers: $1 \leq N \leq 4000$ and $0 \leq E \leq 600000$ representing the number of vertices and edges respectively. The second line of standard input contains $N$ integers. The $i^{th}$ integer represents the vertex weight for the $i^{th}$ vertex. All vertex weights are positive and will be not more than 1 000 000. The following $E$ lines each contain a pair of vertex numbers, $x$ and $y$. This denotes that there is an undirected edge connecting vertices $x$ and $y$. It is guaranteed that $x \neq y$.

Output

On the first line, output the total sum of vertex weights in the vertex cover. On the second line, output up to $N$ vertices on a single line. These $N$ vertices should not contain duplicate values and should form a vertex cover. More specifically, all vertex numbers must be within $0$ and $N-1$ and there should not be two of the same vertex number in the line.

Score

Let $Opt$ be the length of an optimal minimum weighted vertex cover, $Val$ be the sum of vertex weights of the vertex cover found by your solution, and $Naive$ be the sum of vertex weights found by the algorithm below.

Define $x=(Val - Opt)/(Naive - Opt)$. (In the special case that $Naive=Opt$, define $x=0$ if $Val=Opt$, and $x=\inf $ if $Val>Opt$.)

The score on a test case is $0.02^{x}$. Thus, if your vertex cover is optimal, you will get 1 point on this test case. If your score is halfway between $Naive$ and $Opt$, you get roughly $0.14$ points. The total score of your submission is the sum of your score over all test cases. There will be a total of $40$ test cases. Thus, an implementation of the algorithm below should give a score of at least $0.8$ (it will get 0.02 points on most test cases, and 1.0 points on some easy cases where it manages to find an optimal solution).

The algorithm giving the value $Naive$ is the as follows:

SimpleWVC(vertices, edges)
  for every edge (u, v) in edges
    if weight[u] < weight[v]
      used[u] = True
    else if weight[u] > weight[v]
      used[v] = True
    else if u < v
      used[u] = True
    else
      used[v] = True
  
  initialize vertex_cover to an empty list
  for i = 0 to n-1
    if used[i]
      append i to vertex_cover
  return vertex_cover

8 9
1 1 999 1 1 1 999 100
0 1
1 2
1 4
2 3
2 5
3 6
4 5
5 6
6 7

103
1 3 5 7