#include <cstdio>
#include <algorithm>
#define maxn 210
#define inf 2000000000

using namespace std;

struct punct {
	int x, y;
};

int n, i, j, mn, k;
int cs[maxn][maxn], a[maxn][maxn], b[maxn][maxn];
punct v[maxn];

bool cmp(punct a, punct b) {
	if (a.x < b.x)
		return true;
	return false;
}

inline int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int main() {
	freopen("wanted.in", "r", stdin);
	freopen("wanted.out", "w", stdout);

	scanf("%d", &n);

	for (i = 1; i <= n; i++)
		scanf("%d%d", &v[i].x, &v[i].y);

	sort(v + 1, v + n + 1, cmp);

	for (i = 0; i <= n; i++)
		for (j = 0; j <= n; j++)
			cs[i][j] = v[i].y + v[j].y + abs(v[i].x - v[j].x);

	for (i = 1; i <= n; i++) {
		a[i][i] = cs[i - 1][i];
		b[i][i] = cs[i][i + 1];
	}

	for (i = n - 1; i > 0; i--)
		for (j = i + 1; j <= n; j++) {
			mn = inf;
			for (k = i; k <= j; k++)
				if (max(a[k + 1][j] + cs[j + 1][k], b[i][k - 1] + cs[j + 1][k]) < mn)
					mn = max(a[k + 1][j] + cs[j + 1][k], b[i][k - 1] + cs[j + 1][k]);
			b[i][j] = mn;
			

			mn = inf;
			for (k = i; k <= j; k++)
				if (max(a[k + 1][j] + cs[i - 1][k], b[i][k - 1] + cs[i - 1][k]) < mn)
					mn = max(a[k + 1][j] + cs[i - 1][k], b[i][k - 1] + cs[i - 1][k]);
			a[i][j] = mn;
		}

/*	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++)
			printf("%d ", a[i][j]);
		printf("\n");
	}
	printf("\n");

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++)
			printf("%d ", b[i][j]);
		printf("\n");
	}
	printf("\n");*/


	printf("%d\n", a[1][n]);

	return 0;
}