Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Plant Trees, Save Life

By dhruba_1603088 · Limits 1s, 512 MB

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?

Input

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

Output

Print the minimum amount of ice creams you need to finish the work.

Sample

InputOutput
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
15

Discussion

Statistics


62% Solution Ratio

nahidhasan98Earliest, Oct '19

rumi_23Fastest, 0.0s

subhashis_cseLightest, 524 kB

lelbabaShortest, 545B

Submit

Login to submit

Editorial

Use DSU to calculate the sum of minimum values in every connected component.

Toph uses cookies. By continuing you agree to our Cookie Policy.