#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("wanted.in");
ofstream fout("wanted.out");
const int oo = 2000000000;
int N;
pair <int,int> P[205];
int DP[205][205][2];
void Read()
{
    fin >> N;
    for(int i = 1; i <= N; ++i)
    {
        fin >> P[i].first >> P[i].second;
    }
    sort(P+1,P+N+1);
}

int Distance(int Left, int Right)
{
    return P[Left].second + P[Right].second + abs(P[Left].first-P[Right].first);
}

int Find(int Left, int Right,int Direction)
{

if(Left > Right)
{
    return 0;
}

if(DP[Left][Right][Direction] == oo)
for(int k = Left; k <= Right; ++k)
{
    if(Direction == 0)
        DP[Left][Right][0] = min(DP[Left][Right][0],max(Find(Left,k-1,1),Find(k+1,Right,0))+Distance(Left-1,k));
    else
        DP[Left][Right][1] = min(DP[Left][Right][1],max(Find(Left,k-1,1),Find(k+1,Right,0))+Distance(Right+1,k));
}

return DP[Left][Right][Direction];
}

void Print()
{
    fout << Find(1,N,0)<<"\n";
}

int main()
{
    Read();
    for(int i = 0; i <= N; ++i)
        for(int j = 0; j <= N; ++j)
            {
                DP[i][j][0] = oo;
                DP[i][j][1] = oo;
            }
    Print();
    return 0;
}