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.
Constraints
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
Comments