374 . 島嶼
TopCoder
Description
你來到一個有 $n$ 個島嶼的國家，這些島嶼編號為 $1$ 到 $n$。
現在這個國家需要建一些橋，讓 $n$ 座島嶼間都能透過這些橋互相往來。但是，建橋需要花很多錢，於是請你來幫忙規劃，以節省花費。
每座島嶼有兩個參數 $p_i$ 和 $d_i$。島嶼 $i$ 只能連接最多 $d_i$ 座橋，而建一座連接島嶼 $i$ 和島嶼 $j$ 的橋需要花費 $|p_i - p_j|$。 請注意，在給定的條件下，有可能沒辦法讓這些島嶼透過橋互相連接。
Input Format
輸入的第一行包含一個正整數 $T (T \leq 60)$，代表測試資料的數量。
每筆測試資料的第一行包含一個正整數 $n(2 \leq n \leq 4000)$，表示島嶼數量。 接續共有 $n$ 行，每行當中都包含兩個正整數，其中的第 $i$ 行包含的便是代表島嶼 $i$ 的兩個參數的 $p_i(1 \leq p_i \leq 10^9)$ 和 $d_i(1 \leq d_i \leq n)$。
Output Format
對於每筆測資，在獨立的一行中輸出建設橋以連接所有島嶼所需的最小花費，若無法辦到，則輸出 $-1$。
Sample Input 1
4
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
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
Sample Output 1
18
634
-1
916
634
-1
916
Hints
Problem Source
NEOJ Problem 422
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 100 |