TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4295
  • Problem
  • P4295云消雾散
    Limits : Time Limit : - MS   Memory Limit : 65536 KB
    Judgment Tips : 1s
    Description

    在玩完致郁游戏《starkmalの呗》之后,E100WT的心灵受到了极大的冲击,于是他决定睡觉重启大脑。在睡梦中,E100WT梦见了自称为大爷的神秘男子,并教会了他神技——云消雾散。醒来后,为了加深对技能的熟练度,E100WT决定将家里用m条数据线连接起来的仅有的n块主板拿来当靶子。E100WT已经穷到两块主板之间最多只有一根数据线连接了。每一次对主板使用这个技能,都能消除这块主板以及与其直接连接的所有数据线。主板被消除当然会让E100WT心疼咯,所以每块主板都有其各自的心疼值(可能重复)。每一次使用这个技能,立即消除一个主板,E100WT增加的心疼值是与该主板消失前直接连接着的仍存在的主板的心疼值之和(已经消失了的不纳入统计)。

    这些主板很多都是E100WT捡来的,所以E100WT狠下心决定把它们全部消除。但是E100WT并不想让自己太心疼,请问完成整个过程E100WT的心疼值最少是多少?

    Input Format

    第一行两个整数n, m. n表示主板个数,m表示总的数据线条数;

    第二行n个用空格隔开的整数, 第i个数是第i块主板的心疼值;

    接下来m行,每行两个整数a, b,分别是数据线连接的两块主板编号。

    Output Format

    一个整数,表示心疼值的最小值

    Sample Input

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

    Sample Output

    40

    Hint

    对于50%的数据,n <= 10,000

    对于100%的数据,n <=700,000,m <= 800,000

    输入数据保证初始状态主板相连通。保证答案不会超过 2^63-1


    Source  EW100T