#include <fstream>
#include <algorithm>
#include <math.h>
using namespace std;

ifstream cin("wanted.in");
ofstream cout("wanted.out");

const int NMAX = 205;

int dp[NMAX][NMAX][3], cost[NMAX][NMAX];

pair<int, int> vals[NMAX];

int recursivCaAsaVreauEu(int st, int dr, int cazuLuPetricaVoievod){
    if(st > dr)
        return 0;///nu mere vere
    if(dp[st][dr][cazuLuPetricaVoievod] == 10000000){
        for(int k = st; k <= dr; k ++){
            int val = max(recursivCaAsaVreauEu(st, k - 1, 1), recursivCaAsaVreauEu(k + 1, dr, 0));
           switch(cazuLuPetricaVoievod){
               case 0:
                    dp[st][dr][cazuLuPetricaVoievod] = min(dp[st][dr][cazuLuPetricaVoievod], val + abs(vals[k].first - vals[st - 1].first) + vals[k].second + vals[st - 1].second);
                    break;
                case 1:
                    dp[st][dr][cazuLuPetricaVoievod] = min(dp[st][dr][cazuLuPetricaVoievod], val + abs(vals[k].first - vals[dr + 1].first) + vals[k].second + vals[dr + 1].second);
                    break;
           }
        }
    }
    return dp[st][dr][cazuLuPetricaVoievod];
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i<= n; i ++){
        cin >> vals[i].first >> vals[i].second;
    }
    sort(vals + 1, vals + n + 1);
    for(int i = 1; i <= n; i ++){
        for(int j =1 ; j <= n; j ++){
            if(j != i)
            cost[i][j] = abs(vals[i].first - vals[j].first);
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            dp[i][j][1] = dp[i][j][0] = 10000000;
        }
    }
    cout << recursivCaAsaVreauEu(1, n, 0);
    return 0;
}