Another Contest 7 Problem 3 - Network Connections

View as PDF

Points: 10 (partial)
Time limit: 0.75s
Memory limit: 256M

Problem type

Ren has recently created a website, Ternary Search, which he intends on turning into the premier platform for competitive programmers to talk about anything.

Ren's website has slowly become more and more popular - it currently has users, user having a unique friendliness value that is a positive integer no larger than one billion.

Ren wants to make sure that any user is able to communicate with any other user on the platform. Two users can directly communicate with each other if and only if they are friends, so two users and can communicate if they are friends with each other, or if there is some sequence of users such that adjacent users in the sequence are friends.

Ren knows which users are friends with each other, and can force users and to be friends with cost . Compute the minimum cost Ren needs to incur such that any two users on the platform can communicate with each other.

Input Specification

The first line contains two space-separated positive integers and .

The next line contains space-separated integers, the values for the users in order.

The next lines each contain two space-separated integers and , indicating that users and user are already friends. It is guaranteed that every friendship already present is expressed exactly once.

Output Specification

Output the minimum cost needed to make sure any two users can communicate.

Sample Input

4 2
1 2 3 4
1 2
3 4

Sample Output

1