← 返回题目列表

Codeforces · 733/F

F. 司机不满意

中文机器翻译题面 查看原题

在一个王国里有 n 个城市和 m 条双向道路。每条道路连接一对城市,对于每条道路,我们都知道驾驶员的不满程度 - 值 wi。

对于每条路,我们都知道其值 ci – 我们应该花费多少 lamzik​​ 来将对这条路的不满意程度降低 1。因此,为了减少对第i条路的不满k,我们应该花费k·ci lamzik​​s。并且允许不满为零甚至为负。

按照国王的命令,我们需要选择n-1条道路并将其作为主干道。必须满足一个重要条件:应该可以通过主要道路从任何城市前往任何其他城市。

公路部有 S lamzik​​s 的预算用于改革。该部将把这笔预算用于修复一些道路(以减少对它们的不满),然后选择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 的成本(以 lamzik​​s 为单位)。

接下来的 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