{"raw_statement":[{"iden":"statement","content":"In one kingdom there are _n_ cities and _m_ two-way roads. Each road connects a pair of cities, and for each road we know the level of drivers dissatisfaction — the value _w__i_.\n\nFor each road we know the value _c__i_ — how many lamziks we should spend to reduce the level of dissatisfaction with this road by one. Thus, to reduce the dissatisfaction with the _i_\\-th road by _k_, we should spend _k_·_c__i_ lamziks. And **it is allowed for the dissatisfaction to become zero or even negative**.\n\nIn accordance with the king's order, we need to choose _n_ - 1 roads and make them the _main roads_. An important condition must hold: it should be possible to travel from any city to any other by the _main roads_.\n\nThe road ministry has a budget of _S_ lamziks for the reform. The ministry is going to spend this budget for repair of some roads (to reduce the dissatisfaction with them), and then to choose the _n_ - 1 _main roads_.\n\nHelp to spend the budget in such a way and then to choose the main roads so that the total dissatisfaction with the _main roads_ will be as small as possible. The dissatisfaction with some roads can become negative. It is not necessary to spend whole budget _S_.\n\nIt is guaranteed that it is possible to travel from any city to any other using existing roads. Each road in the kingdom is a two-way road."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 2·105, _n_ - 1 ≤ _m_ ≤ 2·105) — the number of cities and the number of roads in the kingdom, respectively.\n\nThe second line contains _m_ integers _w_1, _w_2, ..., _w__m_ (1 ≤ _w__i_ ≤ 109), where _w__i_ is the drivers dissatisfaction with the _i_\\-th road.\n\nThe third line contains _m_ integers _c_1, _c_2, ..., _c__m_ (1 ≤ _c__i_ ≤ 109), where _c__i_ is the cost (in lamziks) of reducing the dissatisfaction with the _i_\\-th road by one.\n\nThe next _m_ lines contain the description of the roads. The _i_\\-th of this lines contain a pair of integers _a__i_ and _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_) which mean that the _i_\\-th road connects cities _a__i_ and _b__i_. All roads are two-way oriented so it is possible to move by the _i_\\-th road from _a__i_ to _b__i_, and vice versa. It is allowed that a pair of cities is connected by more than one road.\n\nThe last line contains one integer _S_ (0 ≤ _S_ ≤ 109) — the number of lamziks which we can spend for reforms."},{"iden":"output","content":"In the first line print _K_ — the minimum possible total dissatisfaction with _main roads_.\n\nIn each of the next _n_ - 1 lines print two integers _x_, _v__x_, which mean that the road _x_ is among main roads and the road _x_, after the reform, has the level of dissatisfaction _v__x_.\n\nConsider that roads are numbered from 1 to _m_ in the order as they are given in the input data. The edges can be printed in arbitrary order. If there are several answers, print any of them."},{"iden":"examples","content":"Input\n\n6 9\n1 3 1 1 3 1 2 2 2\n4 1 4 2 2 5 3 1 6\n1 2\n1 3\n2 3\n2 4\n2 5\n3 5\n3 6\n4 5\n5 6\n7\n\nOutput\n\n0\n1 1\n3 1\n6 1\n7 2\n8 -5\n\nInput\n\n3 3\n9 5 1\n7 7 2\n2 1\n3 1\n3 2\n2\n\nOutput\n\n5\n3 0\n2 5"}],"translated_statement":[{"iden":"statement","content":"在一个王国中，有 #cf_span[n] 座城市和 #cf_span[m] 条双向道路。每条道路连接一对城市，且每条道路都有一个司机不满值 —— 值为 #cf_span[wi]。\n\n对于每条道路，我们已知值 #cf_span[ci] —— 为将该道路的不满值减少一单位所需花费的 lamziks 数量。因此，要将第 #cf_span[i] 条道路的不满值减少 #cf_span[k]，需要花费 #cf_span[k·ci] lamziks。*允许不满值变为零甚至负数*。\n\n根据国王的命令，我们需要选择 #cf_span[n - 1] 条道路作为 _主干道路_。必须满足一个重要条件：通过 _主干道路_，可以从任意一座城市到达任意其他城市。\n\n道路部的改革预算为 #cf_span[S] lamziks。该部门将用这笔预算修复部分道路（以降低其不满值），然后选择 #cf_span[n - 1] 条 _主干道路_。\n\n请帮助合理分配预算，然后选择主干道路，使得 _主干道路_ 的总不满值尽可能小。某些道路的不满值可以变为负数。不必用完全部预算 #cf_span[S]。\n\n保证使用现有道路可以从任意城市到达任意其他城市。王国中的每条道路均为双向道路。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 2·105], #cf_span[n - 1 ≤ m ≤ 2·105]) —— 城市数量和王国中道路的数量。\n\n第二行包含 #cf_span[m] 个整数 #cf_span[w1, w2, ..., wm] (#cf_span[1 ≤ wi ≤ 109])，其中 #cf_span[wi] 表示第 #cf_span[i] 条道路的司机不满值。\n\n第三行包含 #cf_span[m] 个整数 #cf_span[c1, c2, ..., cm] (#cf_span[1 ≤ ci ≤ 109])，其中 #cf_span[ci] 表示将第 #cf_span[i] 条道路的不满值减少一单位所需的花费（lamziks）。\n\n接下来的 #cf_span[m] 行描述了道路。第 #cf_span[i] 行包含一对整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi])，表示第 #cf_span[i] 条道路连接城市 #cf_span[ai] 和 #cf_span[bi]。所有道路均为双向，因此可以通过第 #cf_span[i] 条道路从 #cf_span[ai] 到 #cf_span[bi]，反之亦然。允许两个城市之间存在多条道路。\n\n最后一行包含一个整数 #cf_span[S] (#cf_span[0 ≤ S ≤ 109]) —— 可用于改革的 lamziks 数量。\n\n第一行输出 #cf_span[K] —— _主干道路_ 的最小可能总不满值。\n\n接下来的 #cf_span[n - 1] 行中，每行输出两个整数 #cf_span[x, vx]，表示第 #cf_span[x] 条道路是主干道路之一，且经过改造后其不满值为 #cf_span[vx]。\n\n道路编号从 #cf_span[1] 到 #cf_span[m]，按输入顺序排列。边的输出顺序任意。如果有多个答案，输出任意一个即可。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 2·105], #cf_span[n - 1 ≤ m ≤ 2·105]) —— 城市数量和王国中道路的数量。第二行包含 #cf_span[m] 个整数 #cf_span[w1, w2, ..., wm] (#cf_span[1 ≤ wi ≤ 109])，其中 #cf_span[wi] 表示第 #cf_span[i] 条道路的司机不满值。第三行包含 #cf_span[m] 个整数 #cf_span[c1, c2, ..., cm] (#cf_span[1 ≤ ci ≤ 109])，其中 #cf_span[ci] 表示将第 #cf_span[i] 条道路的不满值减少一单位所需的花费（lamziks）。接下来的 #cf_span[m] 行描述了道路。第 #cf_span[i] 行包含一对整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi])，表示第 #cf_span[i] 条道路连接城市 #cf_span[ai] 和 #cf_span[bi]。所有道路均为双向，因此可以通过第 #cf_span[i] 条道路从 #cf_span[ai] 到 #cf_span[bi]，反之亦然。允许两个城市之间存在多条道路。最后一行包含一个整数 #cf_span[S] (#cf_span[0 ≤ S ≤ 109]) —— 可用于改革的 lamziks 数量。"},{"iden":"output","content":"第一行输出 #cf_span[K] —— _主干道路_ 的最小可能总不满值。接下来的 #cf_span[n - 1] 行中，每行输出两个整数 #cf_span[x, vx]，表示第 #cf_span[x] 条道路是主干道路之一，且经过改造后其不满值为 #cf_span[vx]。道路编号从 #cf_span[1] 到 #cf_span[m]，按输入顺序排列。边的输出顺序任意。如果有多个答案，输出任意一个即可。"},{"iden":"examples","content":"输入6 91 3 1 1 3 1 2 2 24 1 4 2 2 5 3 1 61 21 32 32 42 53 53 64 55 67输出01 13 16 17 28 -5输入3 39 5 17 7 22 13 13 22输出53 02 5"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the number of cities and roads, respectively.  \nLet $ W = (w_1, \\dots, w_m) \\in \\mathbb{Z}_{>0}^m $ be the initial dissatisfaction values of the roads.  \nLet $ C = (c_1, \\dots, c_m) \\in \\mathbb{Z}_{>0}^m $ be the cost per unit dissatisfaction reduction for each road.  \nLet $ E = \\{(a_i, b_i) \\mid i \\in \\{1, \\dots, m\\}\\} $ be the set of road connections (edges) between cities.  \nLet $ S \\in \\mathbb{Z}_{\\geq 0} $ be the budget available for reduction.  \n\nLet $ x_i \\in \\mathbb{Z}_{\\geq 0} $ denote the amount of dissatisfaction reduced on road $ i $, for $ i \\in \\{1, \\dots, m\\} $.  \nThe final dissatisfaction of road $ i $ is $ w_i - x_i $.  \nThe cost of reduction on road $ i $ is $ c_i \\cdot x_i $.  \n\nLet $ T \\subseteq E $ be a spanning tree of the graph with $ n-1 $ edges.  \n\n**Constraints**  \n1. $ \\sum_{i=1}^m c_i x_i \\leq S $  \n2. $ x_i \\geq 0 $ for all $ i \\in \\{1, \\dots, m\\} $  \n3. The selected edges $ T $ form a spanning tree: $ |T| = n-1 $, and the subgraph induced by $ T $ is connected and acyclic.  \n\n**Objective**  \nMinimize the total dissatisfaction of the selected spanning tree:  \n$$\n\\min_{T, \\{x_i\\}} \\sum_{i \\in T} (w_i - x_i)\n$$  \nsubject to the above constraints.","simple_statement":null,"has_page_source":false}