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

#define max(a, b) ( ( a>b ) ? a : b )
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];

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

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;
		}
	
	printf("%d\n", a[1][n]);

	return 0;
}