{"raw_statement":[{"iden":"problem statement","content":"You are given a simple undirected graph with $N$ vertices and $M$ edges. The $i$\\-th edge connects Vertices $U_i$ and $V_i$. Vertex $i$ has a positive integer $A_i$ written on it.\nYou will repeat the following operation $N$ times.\n\n*   Choose a Vertex $x$ that is not removed yet, and remove Vertex $x$ and all edges incident to Vertex $x$. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex $x$ that are not removed yet.\n\nWe define the cost of the entire $N$ operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations."},{"iden":"constraints","content":"*   $1 \\le N \\le 2 \\times 10^5$\n*   $0 \\le M \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le 10^9$\n*   $1 \\le U_i,V_i \\le N$\n*   The given graph is simple.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$"},{"iden":"sample input 1","content":"4 3\n3 1 4 2\n1 2\n1 3\n4 1"},{"iden":"sample output 1","content":"3\n\nBy performing the operations as follows, the maximum of the costs of the $N$ operations can be $3$.\n\n*   Choose Vertex $3$. The cost is $A_1=3$.\n*   Choose Vertex $1$. The cost is $A_2+A_4=3$.\n*   Choose Vertex $2$. The cost is $0$.\n*   Choose Vertex $4$. The cost is $0$.\n\nThe maximum of the costs of the $N$ operations cannot be $2$ or less, so the solution is $3$."},{"iden":"sample input 2","content":"7 13\n464 661 847 514 74 200 188\n5 1\n7 1\n5 7\n4 1\n4 5\n2 4\n5 2\n1 3\n1 6\n3 5\n1 2\n4 6\n2 7"},{"iden":"sample output 2","content":"1199"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}