There are n students in a school. Some of them are friends with each other. You want to make the school clean. So you have to give ice-cream to each student so he or she starts planting trees.
When one plants a tree, he/she tells it to all of his friends and they start to plant trees and tell their friends too (without any ice creams) and so on.
i-th student wants xi ice creams in exchange for starting the trend.
Your work is finished when all n students start planting trees. What is the minimum number of ice creams you need to distribute to finish the work?
The first line contains two integer numbers n and k — the number of students and the number of pairs of friends.
The second line contains n integer numbers xi (0 <= xi <= 109)
Then there will be k lines. Each will contain a pair of numbers(a,b) where a and b are friends (1 <= a,b <= n) and a is not equal to b.
Constrains:
For 10 points: 1 ≤ n ≤ 700, 0 ≤ k ≤ 300
For 40 points: 1 ≤ n ≤ 105, 0 ≤ k ≤ 1200
For 100 points: 1 ≤ n ≤ 105, 0 ≤ k ≤ 105
Print the minimum amount of ice creams you need to finish the work.
Input | Output |
---|---|
10 5 1 6 2 7 3 8 4 9 5 10 1 2 3 4 5 6 7 8 9 10 | 15 |