#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<bitset>
#include<algorithm>
#include<iterator>
#include<stack>
#include<cstring>
#include<cmath>

using namespace std;

ifstream f("wanted.in");
ofstream g("wanted.out");

int Memo[205][205][3];
pair <int, int> V[205];
int n;
int const oo = 1000000000;

void Read()
{
    int i;

    f>>n;
    for(i=1; i<=n; i++)
        f>>V[i].first>>V[i].second;
}

int Distance(int i, int j)
{
   return (V[i].second + V[j].second + abs(V[i].first - V[j].first));
}

int DIM(int l, int r, int direction)
{
    if(Memo[l][r][direction] != oo)
        return Memo[l][r][direction];

    for(int i=l; i<=r; i++){
        if(direction == 0)
            Memo[l][r][direction] = min(Memo[l][r][direction], max(DIM(l, i-1, 1), DIM(i + 1, r, 0)) + Distance(l-1, i) );
        if(direction == 1)
            Memo[l][r][direction] = min(Memo[l][r][direction], max(DIM(l, i-1, 1), DIM(i + 1, r, 0)) + Distance(r+1, i) );
    }

    return Memo[l][r][direction];
}

void Solve()
{
    int i, j, k;

    sort(V + 1, V + n + 1);
    for(i=1; i<=n; i++)
        for(j=i; j<=n; j++)
            for(k=0; k<=1; k++)
                Memo[i][j][k] = oo;

    DIM(1, n, 0);

    g<<Memo[1][n][0]<<"\n";
}

int main()
{
    Read();
    Solve();
    return 0;
}