{"problem":{"name":"Erasing Vertices 2","description":{"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. You will repeat the ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc267_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc267_e","tags":[],"sample_group":[["4 3\n3 1 4 2\n1 2\n1 3\n4 1","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$."],["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","1199"]],"created_at":"2026-03-03 11:01:14"}}