떠 있는 섬

작은 나라에 막 도착했다. 며칠 전 거대한 허리케인이 이 나라를 휩쓸고 지나갔다.

이 나라는 $1$번부터 $n$번까지 번호가 붙은 섬 $n$개로 이루어져 있다. 예전에는 많은 다리가 섬을 이어 주었지만, 홍수에 다리가 모두 떠내려갔다. 주민이 다시 섬 사이를 오가려면 새 다리가 필요하다.

문제는 비용이다. 나라 살림이 넉넉하지 않아 정부는 지출을 줄여야 한다. 정부는 뛰어난 프로그래머인 당신에게 다리를 다시 놓는 최소 비용을 계산해 달라고 부탁했다.

다리 하나는 섬 두 개를 양방향으로 잇는다. 섬 $i$에는 두 값 $p_i$와 $d_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 \le n \le 4000$)은 섬의 개수다. 이어지는 $n$개의 줄에는 각 섬의 값이 주어지며, $p_i$ ($1 \le p_i \le 10^9$)와 $d_i$ ($1 \le d_i \le n$)는 섬 $i$의 두 값이다.

입력의 끝은 $0$ 하나만 있는 줄로 나타낸다.

각 데이터 집합마다, 주어진 제한 안에서 다리를 다시 놓을 수 있으면 최소 비용을 한 줄에 출력한다. 불가능하면 $-1$을 한 줄에 출력한다.