CF733F.Drivers Dissatisfaction

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.

For 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.

In 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.

The 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.

Help 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.

It 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.

某个王国中有 $n$ 座城市和 $m$ 条双向道路。每条道路连接一对城市，且对每条道路，我们已知司机的不满程度——其值为 $w_i$。

对每条道路，我们还知道值 $c_i$ —— 即为将该道路的不满程度降低 1 所需花费的“拉姆齐克”（lamziks）数量。因此，若要将第 $i$ 条道路的不满程度降低 $k$，则需花费 $k \cdot c_i$ 个拉姆齐克。不满程度允许降至零甚至负数。

根据国王的命令，我们需要从所有道路中选出 $n-1$ 条作为主干道。一个关键约束条件是：仅通过这些主干道，必须能从任意一座城市到达其余任意一座城市（即主干道构成一棵生成树）。

道路部此次改革的预算是 $S$ 个拉姆齐克。该部门计划将这笔预算用于部分道路的修缮（以降低其不满程度），随后再从中选定 $n-1$ 条主干道。

请设计一种预算分配方案，并在修缮后选择主干道，使得所选主干道的总不满程度尽可能小。某些道路的不满程度可为负数。无需用尽全部预算 $S$。

题目保证：利用现有道路，可从任意城市抵达其余任意城市。王国中每条道路均为双向道路。

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.

The 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.

The 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.

The 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.

The last line contains one integer S (0 ≤ S ≤ 109) — the number of lamziks which we can spend for reforms.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2\cdot10^5$，$n - 1 \leq m \leq 2\cdot10^5$），分别表示王国中的城市数量和道路数量。

第二行包含 $m$ 个整数 $w_1,\,w_2,\,\dots,\,w_m$（$1 \leq w_i \leq 10^9$），其中 $w_i$ 表示司机对第 $i$ 条道路的不满值。

第三行包含 $m$ 个整数 $c_1,\,c_2,\,\dots,\,c_m$（$1 \leq c_i \leq 10^9$），其中 $c_i$ 表示将第 $i$ 条道路的不满值降低 $1$ 所需的花费（单位：lamziks）。

接下来 $m$ 行描述各条道路。其中第 $i$ 行包含一对整数 $a_i$ 和 $b_i$（$1 \leq a_i,\,b_i \leq n$，$a_i \neq b_i$），表示第 $i$ 条道路连接城市 $a_i$ 和 $b_i$。所有道路均为双向通行，即可以从 $a_i$ 经第 $i$ 条道路到达 $b_i$，反之亦然。允许同一对城市之间存在多条道路。

最后一行包含一个整数 $S$（$0 \leq S \leq 10^9$）——可用于改革的 lamziks 总数。

In the first line print K — the minimum possible total dissatisfaction with main roads.

In 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.

Consider 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.

第一行输出 K —— 主干道总不满度的最小可能值。

接下来的 n − 1 行中，每行输出两个整数 x, v__x，表示道路 x 被选为主干道，且该道路经改革后的不满度为 v__x。

注意：道路按输入数据中给出的顺序编号为 1 到 m。边的输出顺序可以任意。若存在多个答案，输出任意一个即可。