#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("wanted.in");
ofstream fout("wanted.out");

const int NMax = 200, oo = 1e9;

int DP[NMax + 5][NMax + 5][2], C[NMax + 5][NMax + 5], N;
struct str{int x, y;} V[NMax + 5];

inline bool compare(str A, str B) { return A.x < B.x;}

int Solve(int st, int dr, bool p)
{
    if(st > dr) return 0;
    int K = ((p) ? (dr + 1) : (st - 1)), A, B;

    if(DP[st][dr][p] != oo) return DP[st][dr][p];

    for(int i = st; i <= dr; i++)
    {
        A = Solve(st, i - 1, 1) + C[K][i];
        B = Solve(i + 1, dr, 0) + C[K][i];

        DP[st][dr][p] = min(DP[st][dr][p], max(A, B));
    }
    return DP[st][dr][p];
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> V[i].x >> V[i].y;

    sort(V + 1, V + N + 1, compare);

    for(int i = 0; i <= N; i++)
        for(int j = 0; j <= N; j++)
            C[i][j] = abs(V[i].x - V[j].x) + V[i].y + V[j].y, DP[i][j][0] = DP[i][j][1] = oo;

    fout << Solve(1, N, 0) << '\n';

    fin.close();
    fout.close();

    return 0;
}