题目描述

你刚到达一个小国家。不幸的是，几天前这个国家被一场巨大的飓风横扫。

该国由 $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```

### 样例输出

```plain
18
634
-1
916```

---

### 资源名称

[JAG Practice Contest for ACM-ICPC Asia Regional 2013](http://acm-icpc.aitea.net/index.php?2013%2FPractice%2F%CC%CF%B5%BC%C3%CF%B6%E8%CD%BD%C1%AA)