#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

template<class T> inline void chmin(T& a, const T& b) { if(b < a) a = b; }

const long long INF = (1ll << 60);

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	for(int n; cin >> n && n;) {
		if(n == 2) {
			int p1, d1, p2, d2;
			cin >> p1 >> d1 >> p2 >> d2;
			cout << abs(p1 - p2) << endl;
			continue;
		}

		vector<int> single;
		vector<pair<int, int>> multiple;

		single.reserve(n);
		multiple.reserve(n);

		for(int i = 0; i < n; ++i) {
			int p, d;
			cin >> p >> d;

			if(d == 1) single.emplace_back(p);
			else multiple.emplace_back(p, d);
		}

		sort(single.begin(), single.end());
		sort(multiple.begin(), multiple.end());

		long long cost = 0;
		for(int i = 0; i < static_cast<int>(multiple.size()) - 1; ++i) {
			--multiple[i].second;
			--multiple[i + 1].second;
			cost += abs(multiple[i].first - multiple[i + 1].first);
		}

		if(single.size() == 0) {
			cout << cost << endl;
			continue;
		}

		vector<int> m_pos;
		m_pos.reserve(n * n);
		for(const auto &m_island : multiple) {
			for(int j = 0; j < m_island.second; ++j) {
				m_pos.emplace_back(m_island.first);
			}
		}

		const int s_size = single.size();
		const int m_size = m_pos.size();

		if(s_size > m_size) {
			cout << -1 << endl;
			continue;
		}

		vector<int> near(s_size);
		for(int i = 0; i < s_size; ++i) {
			near[i] = lower_bound(m_pos.begin(), m_pos.end(), single[i]) - m_pos.begin();
		}

		int prev_near = 0;
		const int len = s_size + s_size + 1;
		vector<long long> dp(len, cost);

		for(int i = 0; i < s_size; ++i) {
			const int diff = near[i] - prev_near;
			for(int j = 0; j < len; ++j) {
				dp[j] = dp[min(j + diff, len - 1)];
			}

			vector<long long> tmp(len, INF);
			for(int j = 0; j < len - 1; ++j) {
				const int k = near[i] - s_size + j;
				if(k < 0) continue;
				if(k >= m_size) break;
				chmin(tmp[j + 1], dp[j] + abs(single[i] - m_pos[k]));
			}

			for(int j = 0; j < len - 1; ++j) {
				chmin(tmp[j + 1], tmp[j]);
			}

			dp = move(tmp);
			prev_near = near[i];
		}

		cout << dp.back() << endl;
	}

	return EXIT_SUCCESS;
}
### Prompt

Your task is to create a cpp solution to the following problem:

Problem Statement

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

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

The problem is cost. The country is not very wealthy. The government has to keep spending down. They asked you, a great programmer, to calculate the minimum cost to rebuild bridges. Write a program to calculate it!

Each bridge connects two islands bidirectionally. Each island $i$ has two parameters $d_i$ and $p_i$. An island $i$ can have at most $d_i$ bridges connected. The cost to build a bridge between an island $i$ and another island $j$ is calculated by $|p_i - p_j|$. Note that it may be impossible to rebuild new bridges within given limitations although people need to travel between any pair of islands over (a sequence of) bridges.

Input

The input is a sequence of datasets. The number of datasets is less than or equal to $60$. Each dataset is formatted as follows.

> $n$
> $p_1$ $d_1$
> $p_2$ $d_2$
> :
> :
> $p_n$ $d_n$

Everything in the input is an integer. $n$ ($2 \leq n \leq 4{,}000$) on the first line indicates the number of islands. Then $n$ lines follow, which contain the parameters of the islands. $p_i$ ($1 \leq p_i \leq 10^9$) and $d_i$ ($1 \leq d_i \leq n$) denote the parameters of the island $i$.

The end of the input is indicated by a line with a single zero.

Output

For each dataset, output the minimum cost in a line if it is possible to rebuild bridges within given limitations in the dataset. Otherwise, output $-1$ in a line.

Sample Input


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

Output for the Sample Input


18
634
-1
916





Example

Input

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


Output

18
634
-1
916

### Response

```cpp
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

template<class T> inline void chmin(T& a, const T& b) { if(b < a) a = b; }

const long long INF = (1ll << 60);

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	for(int n; cin >> n && n;) {
		if(n == 2) {
			int p1, d1, p2, d2;
			cin >> p1 >> d1 >> p2 >> d2;
			cout << abs(p1 - p2) << endl;
			continue;
		}

		vector<int> single;
		vector<pair<int, int>> multiple;

		single.reserve(n);
		multiple.reserve(n);

		for(int i = 0; i < n; ++i) {
			int p, d;
			cin >> p >> d;

			if(d == 1) single.emplace_back(p);
			else multiple.emplace_back(p, d);
		}

		sort(single.begin(), single.end());
		sort(multiple.begin(), multiple.end());

		long long cost = 0;
		for(int i = 0; i < static_cast<int>(multiple.size()) - 1; ++i) {
			--multiple[i].second;
			--multiple[i + 1].second;
			cost += abs(multiple[i].first - multiple[i + 1].first);
		}

		if(single.size() == 0) {
			cout << cost << endl;
			continue;
		}

		vector<int> m_pos;
		m_pos.reserve(n * n);
		for(const auto &m_island : multiple) {
			for(int j = 0; j < m_island.second; ++j) {
				m_pos.emplace_back(m_island.first);
			}
		}

		const int s_size = single.size();
		const int m_size = m_pos.size();

		if(s_size > m_size) {
			cout << -1 << endl;
			continue;
		}

		vector<int> near(s_size);
		for(int i = 0; i < s_size; ++i) {
			near[i] = lower_bound(m_pos.begin(), m_pos.end(), single[i]) - m_pos.begin();
		}

		int prev_near = 0;
		const int len = s_size + s_size + 1;
		vector<long long> dp(len, cost);

		for(int i = 0; i < s_size; ++i) {
			const int diff = near[i] - prev_near;
			for(int j = 0; j < len; ++j) {
				dp[j] = dp[min(j + diff, len - 1)];
			}

			vector<long long> tmp(len, INF);
			for(int j = 0; j < len - 1; ++j) {
				const int k = near[i] - s_size + j;
				if(k < 0) continue;
				if(k >= m_size) break;
				chmin(tmp[j + 1], dp[j] + abs(single[i] - m_pos[k]));
			}

			for(int j = 0; j < len - 1; ++j) {
				chmin(tmp[j + 1], tmp[j]);
			}

			dp = move(tmp);
			prev_near = near[i];
		}

		cout << dp.back() << endl;
	}

	return EXIT_SUCCESS;
}
```