← 返回题目列表

Codeforces · 746/G

G. 新道路

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

Berland有n个城市,每个城市都有一个唯一的id——从1到n的整数,首都是id为1的城市。现在Berland有一个严重的道路问题——没有道路。

这就是为什么决定修建 n - 1 条道路,以便每对城市之间只有一条简单的路径。

在建设计划中规定了t整数a1,a2,...,at,其中t等于从首都到最远城市的距离,涉及新道路。 ai 等于距离首都 i 的城市数量。两个城市之间的距离是指从一个城市到另一个城市必须经过的道路数量。

此外,还决定在除首都之外的所有城市中,应该有正好 k 个城市,每个城市只有一条道路。这样的城市是死胡同,在经济上不具有吸引力。在计算这些城市时,无论从首都出发的道路有多少,都不会被考虑在内。

您的任务是提供满足所有描述条件的道路建设计划,或者告知这是不可能的。

输入

第一行包含三个正数 n、t 和 k (2 ≤ n ≤ 2·105, 1 ≤ t, k < n)——距首都最远城市的距离以及应为死胡同的城市数量(此数字中的首都不考虑在内)。

第二行包含 t 个整数 a1, a2, ... 的序列,在 (1 ≤ ai < n) 处,第 i 个数字是距首都距离为 i 的城市的数量。保证所有值 ai 的总和等于 n - 1。

输出

如果不可能建造满足所有条件的道路,则打印-1。

否则,在第一行打印一个整数 n — Berland 的城市数量。在接下来的 n - 1 行中,每一行打印两个整数——由道路连接的城市的 ID。每条路都应该打印一次。您可以按任意顺序打印道路和道路连接的城市。

如果有多个答案,请打印其中任何一个。请记住,首都的 id 为 1。

示例

输入 #1

7 3 3
2 3 1

输出 #1

7
1 3
2 1
2 6
2 4
7 4
3 5

输入 #2

14 5 6
4 4 2 2 1

输出 #2

14
3 1
1 4
11 6
1 2
10 13
6 10
10 12
14 12
8 4
5 1
3 7
2 6
5 9

输入 #3

3 1 1
2

输出 #3

-1