#include <iostream>
#include <cstdio>

#define NMax 205
#define Inf 2000000005

using namespace std;

int N, X[NMax], Y[NMax], Best[NMax][NMax][NMax];

void Read ()
{
    freopen ("wanted.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d %d", &X[i], &Y[i]);
    }
}

inline int Min (int a, int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

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

inline int Dist (int a, int b)
{
    if (a==b)
    {
        return 0;
    }
    return (Y[a]+Y[b]+Max (X[a]-X[b], X[b]-X[a]));
}

int Memo (int L, int R, int P)
{
    if (L>R)
    {
        Best[L][R][P]=0;
        return 0;
    }
    if (Best[L][R][P]<Inf)
    {
        return Best[L][R][P];
    }
    for (int i=L; i<=R; ++i)
    {
        Best[L][R][P]=Min (Best[L][R][P], Max (Memo (L, i-1, i), Memo (i+1, R, i))+Dist (P, i));
    }
    return Best[L][R][P];
}

void Print ()
{
    freopen ("wanted.out", "w", stdout);
    printf ("%d\n", Memo (1, N, 0));
}

int main()
{
    Read ();
    for (int i=0; i<=N; ++i)
    {
        for (int j=0; j<=N; ++j)
        {
            for (int k=0; k<=N; ++k)
            {
                Best[i][j][k]=Inf;
            }
        }
    }
    Print ();
    return 0;
}