在一个王国里有 n 个城市和 m 条双向道路。每条道路连接一对城市,对于每条道路,我们都知道驾驶员的不满程度 - 值 wi。
对于每条路,我们都知道其值 ci – 我们应该花费多少 lamzik 来将对这条路的不满意程度降低 1。因此,为了减少对第i条路的不满k,我们应该花费k·ci lamziks。并且允许不满为零甚至为负。
按照国王的命令,我们需要选择n-1条道路并将其作为主干道。必须满足一个重要条件:应该可以通过主要道路从任何城市前往任何其他城市。
公路部有 S lamziks 的预算用于改革。该部将把这笔预算用于修复一些道路(以减少对它们的不满),然后选择n-1条主要道路。
帮助以这样的方式花费预算,然后选择主要道路,以便对主要道路的总不满将尽可能小。对某些道路的不满可能会变成负面的。没有必要花费全部预算S。
保证可以使用现有道路从任何城市前往任何其他城市。王国里的每条路都是双向的。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105)——分别是王国的城市数量和道路数量。
第二行包含 m 个整数 w1, w2, ..., wm (1 ≤ wi ≤ 109),其中 wi 是驾驶员对第 i 条道路的不满意程度。
第三行包含 m 个整数 c1, c2, ..., cm (1 ≤ ci ≤ 109),其中 ci 是将第 i 条路的不满度降低 1 的成本(以 lamziks 为单位)。
接下来的 m 行包含道路的描述。该行的第 i 行包含一对整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi),这意味着第 i 条道路连接城市 ai 和 bi。所有道路都是双向的,因此可以通过第 i 条道路从 ai 移动到 bi,反之亦然。允许两个城市由多条道路连接。
最后一行包含一个整数 S (0 ≤ S ≤ 109) — 我们可以用于改革的 lamzik 数量。
输出
在第一行中打印 K — 对主要道路的最小可能总体不满。
在接下来的n-1行中,每一行打印两个整数x,vx,这意味着该道路x属于主干道,并且该道路x在改革后的不满意程度为vx。
考虑道路按照输入数据中给出的顺序从 1 到 m 编号。边缘可以按任意顺序打印。如果有多个答案,请打印其中任何一个。
示例
输入 #1
6 9 1 3 1 1 3 1 2 2 2 4 1 4 2 2 5 3 1 6 1 2 1 3 2 3 2 4 2 5 3 5 3 6 4 5 5 6 7
输出 #1
0 1 1 3 1 6 1 7 2 8 -5
输入 #2
3 3 9 5 1 7 7 2 2 1 3 1 3 2 2
输出 #2
5 3 0 2 5