问题陈述
你刚刚到达一个小国家。不幸的是,几天前一场巨大的飓风席卷了全国。
该国家由 $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