← 返回题目列表

AtCoder · icpc2013autumn_g

G. 漂浮岛屿

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

问题陈述

你刚刚到达一个小国家。不幸的是,几天前一场巨大的飓风席卷了全国。

该国家由 $n$ 个岛屿组成,编号为 $1$ 到 $n$。许多桥梁连接着岛屿,但所有桥梁都被洪水冲毁了。岛上的人们需要新的桥梁才能再次在岛屿之间出行。

问题是成本。这个国家并不是很富裕。政府必须继续削减开支。他们要求你,一个伟大的程序员,计算重建桥梁的最低成本。写个程序来计算一下吧!

每座桥都双向连接两个岛屿。每个岛 $i$ 有两个参数 $d_i$ 和 $p_i$。一个岛屿 $i$ 最多可以连接 $d_i$ 座桥梁。在一个岛 $i$ 和另一个岛 $j$ 之间建造桥梁的成本由 $|p_i - p_j|$ 计算。请注意,尽管人们需要通过(一系列)桥梁在任何一对岛屿之间旅行,但在给定的限制内可能无法重建新的桥梁。


输入

输入是一系列数据集。 数据集数量小于或等于 $60$。 每个数据集的格式如下。

$n$
$p_1$ $d_1$
$p_2$ $d_2$
:
:
$p_n$ $d_n$

输入中的所有内容都是整数。 第一行的 $n$ ($2 \leq n \leq 4{,}000$) 表示岛屿的数量。 接下来是 $n$ 行,其中包含岛屿的参数。 $p_i$ ($1 \leq p_i \leq 10^9$) 和 $d_i$ ($1 \leq d_i \leq n$) 表示岛 $i$ 的参数。

输入的结尾由带有单个零的行指示。

输出

对于每个数据集,如果可以在数据集中的给定限制内重建桥梁,则输出一行中的最小成本。否则,一行输出$-1$。


示例输入

4
1 1
8 2
9 1
14 2
4
181 4
815 4
634 4
370 4
4
52 1
40 1
81 2
73 1
10
330 1
665 3
260 1
287 2
196 3
243 1
815 1
287 3
330 1
473 4
0

样本输入的输出

18
634
-1
916