儿童节,孩子收到了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。