← 返回题目列表

Codeforces · 893/C

C. 谣言

中文机器翻译题面 查看原题

Vova 向自己保证,他永远不会玩电脑游戏……但最近著名游戏开发公司 Firestorm 发布了他们的最新游戏 World of Farcraft,并变得非常受欢迎。当然,Vova开始演奏它。

现在他尝试解决一个任务。任务是来到一个名为Overcity的定居点并在其中传播谣言。

Vova 知道 Overcity 有 n 个角色。有些角色彼此是朋友,他们分享获得的信息。 Vova 还知道他可以贿赂每个角色,这样他或她就开始散布谣言;第 i 个角色想要 ci 金币来换取散布谣言。当一个角色听到谣言时,他会告诉他所有的朋友,然后他们开始向他们的朋友传播谣言(免费),依此类推。

当所有 n 个角色都知道谣言时,任务完成。 Vova 完成任务至少需要花费多少金币?

如果您认为自己还没有完全理解问题,请查看注释。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — Overcity 中的角色数量和好友对的数量。

第二行包含n个整数ci(0≤ci≤109)——第i个字符要求开始散布谣言的金币数量。

接下来是 m 行,每行包含一对数字 (xi, yi),表示字符 xi 和 yi 是朋友(1 ≤ xi, yi ≤ n, xi ≠ yi)。保证每对最多列出一次。

输出

打印一个数字——Vova 完成任务所需花费的最低金币数量。

示例

输入 #1

5 2
2 5 3 4 8
1 4
4 5

输出 #1

10

输入 #2

10 0
1 2 3 4 5 6 7 8 9 10

输出 #2

55

输入 #3

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

输出 #3

15

注意

在第一个示例中,最佳决策是贿赂第一个角色(他将谣言传播给第四个角色,第四个角色将谣言传播给第五个角色)。 Vova 还必须贿赂第二个和第三个角色,让他们知道谣言。

在第二个例子中,Vova 必须贿赂所有人。

在第三个示例中,最佳决策是贿赂第一个、第三个、第五个、第七个和第九个角色。