Tourist Information Points

Time limit1sMemory limit256 MB

Summary

Choose minimum-cost towns so every town holds a point or borders one.

Level: Hard8 of 10
Topics: Dynamic programming, Graph
Solved: No attempts yet

Problem

King Byteasar wants the sights of Byteotia to draw crowds of tourists who spend a lot of money that eventually reaches the royal treasury. Reality falls short of his dream. The king told his councilor to look into it, and the councilor found that foreigners stay away from Byteotia because its road network is sparse.

Byteotia has $n$ towns joined by $m$ two-way roads, and every road links two different towns. Some roads run over flyovers or through tunnels. There is no guarantee that every town can be reached from every other town.

The councilor also observed that the current road network allows no long journey. Wherever you start, you cannot visit more than 10 towns without passing through some town twice.

The treasury cannot pay for new roads, so Byteasar decided to build tourist information points (TIPs) instead, staffed by officers who advertise the short trips that are available. For each town there must be a TIP either in that town or in one of the towns linked to it by a road. The cost of building a TIP is known for each town. Find the cheapest way of building TIPs that satisfies the condition.

Input

The first line contains two integers $n$ and $m$ separated by a single space ( $2 \le n \le 20000$ , $0 \le m \le 25000$ ), the number of towns and the number of roads in Byteotia. The towns are numbered from 1 to $n$ .

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ separated by single spaces ( $0 \le c_i \le 10000$ ), where $c_i$ is the cost of building a TIP in town $i$ .

Each of the next $m$ lines describes one road. The $i$ -th of these lines contains two integers $a_i$ and $b_i$ separated by a single space ( $1 \le a_i < b_i \le n$ ), which means that towns $a_i$ and $b_i$ are linked by a road. There is at most one road between any pair of towns.

In tests worth 20% of the total score, $n \le 20$ holds.

Output

Print one integer on a single line: the total cost of building all the TIPs.

Hint

In the first example the cheapest choice is to build TIPs in towns 1, 5, and 6, at a cost of $3+2+2=7$ .

Examples3

Example 1

Input

6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6

Expected output

Example 2
Input
```
2 0
4 9
```
Expected output
```
13
```
Example 3
Input
```
2 1
5 7
1 2
```
Expected output
```
5
```