← 返回题目列表

Codeforces · 437/C

C. 孩子和玩具

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

儿童节,孩子收到了Delayyy的玩具作为礼物。然而,孩子太调皮了,他迫不及待地想毁掉玩具。

玩具由 n 个部件和 m 根绳子组成。每根绳子连接两个部件,但每对部件最多由一根绳子连接。要拆分玩具,孩子必须拆下玩具的所有部件。孩子一次只能移除一个零件,每次移除都会消耗一个能量。我们将第 i 部分的能量值定义为 vi。孩子花费 vf1 + vf2 + ... + vfk 能量来删除第 i 部分,其中 f1,f2,...,fk 是直接连接到第 i 个且尚未删除的部分。

帮助孩子找出移除所有 n 个零件所需的最小总能量是多少。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000)。第二行包含 n 个整数:v1, v2, ..., vn (0 ≤ vi ≤ 105)。接下来是 m 行,每行包含两个整数 xi 和 yi,表示从 xi 部分到 yi 部分的一条绳子(1 ≤ xi,yi ≤ n;xi ≠ yi)。

考虑所有零件都从 1 到 n 编号。

输出

输出孩子移除玩具的所有 n 个部分所需花费的最小总能量。

示例

输入 #1

4 3
10 20 30 40
1 4
1 2
2 3

输出 #1

40

输入 #2

4 4
100 100 100 100
1 2
2 3
2 4
3 4

输出 #2

400

输入 #3

7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4

输出 #3

160

注意

第一个示例中的最佳操作顺序之一是:

- 首先,删除第 3 部分,该操作的成本为 20。
- 然后,删除第 2 部分,该操作的成本为 10。
- 接下来,删除第 4 部分,操作成本为 10。
- 最后,删除第 1 部分,操作成本为 0。

所以孩子付出的总能量是20 + 10 + 10 + 0 = 40,这是最小值。

在第二个示例中,无论孩子以什么顺序移除零件,他都会花费 400。