{"raw_statement":[{"iden":"statement","content":"Some cities are now occupied. Mr. Light wants to cut all paths that go between specific pairs of cities. Destroying any road on a path cuts that path. The cost of destroying each road di is given.\n\nMr. Light already destroyed some *(one or more)* roads, and the cost for the destroyed roads is given as zero. Find the minimum total cost needed to cut all the paths between the given pairs of cities.\n\nThe first line of input contains two space-separated integers N, M (3 ≤ N ≤ 2 × 105) , the number of cities and the number of pairs to cut the paths between them, respectively.\n\nThe second line of input contains N space-separated integers di (0 ≤ di ≤ 109), the ith value represents the cost of destroying the ith road (or 0 if it is already destroyed).\n\n*It is guaranteed that at least one of the roads is already destroyed.*\n\nEach of the following M lines contains two space-separated integers u, v (1 ≤ u, v ≤ N) (u ≠ v), representing a pair of cities that should not remain connected. No pair of cities will appear more than once.\n\nPrint the minimum cost on a single line.\n\n"},{"iden":"input","content":"The first line of input contains two space-separated integers N, M (3 ≤ N ≤ 2 × 105) , the number of cities and the number of pairs to cut the paths between them, respectively.The second line of input contains N space-separated integers di (0 ≤ di ≤ 109), the ith value represents the cost of destroying the ith road (or 0 if it is already destroyed).*It is guaranteed that at least one of the roads is already destroyed.*Each of the following M lines contains two space-separated integers u, v (1 ≤ u, v ≤ N) (u ≠ v), representing a pair of cities that should not remain connected. No pair of cities will appear more than once."},{"iden":"output","content":"Print the minimum cost on a single line."},{"iden":"examples","content":"Input4 21 0 1 11 42 3Output1Input8 54 0 5 4 5 6 3 01 83 65 88 44 1Output5"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = N $ cities and $ |E| = N-1 $ roads (tree structure implied by connectivity and road count).  \nLet $ d_i \\in \\mathbb{R}_{\\geq 0} $ be the cost of destroying road $ e_i \\in E $, where $ d_i = 0 $ if road $ e_i $ is already destroyed.  \nLet $ P = \\{(u_j, v_j) \\mid j \\in \\{1, \\dots, M\\}\\} $ be a set of $ M $ vertex pairs requiring disconnection.\n\n**Constraints**  \n1. $ 3 \\leq N \\leq 2 \\times 10^5 $  \n2. $ 0 \\leq d_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, N-1\\} $  \n3. At least one $ d_i = 0 $  \n4. For each $ (u_j, v_j) \\in P $, $ u_j \\neq v_j $, and all pairs are distinct.  \n5. The graph is a tree (inferred from $ N $ cities and $ N-1 $ roads, and requirement to disconnect paths).\n\n**Objective**  \nFind the minimum total cost of destroying a subset $ E' \\subseteq E $ such that:  \n- For every pair $ (u_j, v_j) \\in P $, there is no path between $ u_j $ and $ v_j $ in $ G \\setminus E' $.  \n- The cost is $ \\sum_{e_i \\in E'} d_i $, with $ d_i = 0 $ for already destroyed roads.  \n- Minimize $ \\sum_{e_i \\in E'} d_i $.","simple_statement":"You are given a tree with N cities and N-1 roads. Each road has a cost to destroy (0 if already destroyed). You are also given M pairs of cities that must be disconnected. Find the minimum total cost to destroy roads so that all M pairs are disconnected.","has_page_source":false}