Problem descr iption

给定一个赋权无向图G=(V,E)，每个顶点v∈V都有一个权值w(v)。如果U包含于V，且对于(u,v)∈E 有u∈U 且v∈V-U，则有v∈K.如：U = {1}, 若有边（1，2）， 则有2属于K. 若有集合U包含于V使得U + K = V, 就称U 为图G 的一个顶点覆盖。G 的最小权顶点覆盖是指G 中所含顶点权之和最小的顶点覆盖。





Input

输入数据。第1 行有2 个正整数n 和m，表示给定的图G 有n 个顶点和m条边，顶点编号为1，2，…，n。第2 行有n个正整数表示n个顶点的权。接下来的m行中，每行有2 个正整数u,v，表示图G 的一条边(u,v)。





Output

将计算出的最小权顶点覆盖的顶点权之和输出。





Sample Input

7 7

1 100 1 1 1 100 10

1 6

2 4

2 5

3 6

4 5

4 6

6 7



Sample Output

13



-Problem descr iption

　　　　 给定一个赋权无向图G=(V,E)，每个顶点v∈V都有一个权值w(v)。如果U包含于V，且对于(u,v)∈E 有u∈U 且v∈V-U，则有v∈K.如：U = {1}, 若有边（1，2）， 则有2属于K. 若有集合U包含于V使得U+ K = V, 就称U 为图G 的一个顶点覆盖。G 的最小权顶点覆盖是指G 中所含顶点权之和最小的顶点覆盖。





Input

　　　输入数据。第1 行有2 个正整数n 和m，表示给定的图G 有n 个顶点和m条边，顶点编号为1，2，…，n。第2 行有n个正整数表示n个顶点的权。接下来的m行中，每行有2 个正整数u,v，表示图G 的一条边(u,v)。





Output

　将计算出的最小权顶点覆盖的顶点权之和输出。





Sample Input

7 7

1 100 1 1 1 100 10

1 6

2 4

2 5

3 6

4 5

4 6

6 7



Sample Output

13