Floating Islands

You have just arrived in a small country. A huge hurricane swept across it a few days ago.

The country is made up of $n$ islands, numbered $1$ through $n$. Many bridges connected the islands, but the flood washed all of them away. The islanders need new bridges to travel among the islands again.

The problem is cost. The country is not wealthy, so the government has to keep spending down. They asked you, a great programmer, to compute the minimum cost of rebuilding the bridges.

Each bridge connects two islands and can be crossed in both directions. Island $i$ has two parameters $p_i$ and $d_i$. At most $d_i$ bridges can touch island $i$. Building a bridge between island $i$ and island $j$ costs $|p_i - p_j|$. People have to be able to travel between every pair of islands over a sequence of bridges, and the given limits sometimes make that impossible.

The input is a sequence of datasets. The number of datasets is at most $60$. Each dataset has the following format.

n
p_1 d_1
p_2 d_2
...
p_n d_n

Every value in the input is an integer. The first line holds $n$ ($2 \le n \le 4000$), the number of islands. The next $n$ lines hold the parameters of the islands, where $p_i$ ($1 \le p_i \le 10^9$) and $d_i$ ($1 \le d_i \le n$) are the parameters of island $i$.

A line with a single zero marks the end of the input.

For each dataset, print the minimum cost on one line if the bridges can be rebuilt within the given limits. Otherwise print $-1$ on one line.