#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

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

const long long inf = 2000000005;
const int dim = 205;

long long dp[2][dim][dim];
vector< pair<int, int> > v;

constexpr int MyAbs(int x) {
    return (x > 0 ? x : -x);
}

long long Solve(int lef, int rig, int from) {
    bool dir = (lef > from);
    if (lef > rig)
        return 0;
    if (dp[dir][lef][rig] != -1)
        return dp[dir][lef][rig];

    dp[dir][lef][rig] = inf;
    for (int curr = lef; curr <= rig; ++curr) {
        long long temp = max(Solve(lef, curr-1, curr), Solve(curr+1, rig, curr));
        temp += v[from].second + v[curr].second + MyAbs(v[curr].first - v[from].first);

        dp[dir][lef][rig] = min(dp[dir][lef][rig], temp);
    }

    return dp[dir][lef][rig];
}

int main() {

    int n; fin >> n;
    v.assign(n + 1, {0, 0});
    for (int i = 1; i <= n; ++i)
        fin >> v[i].first >> v[i].second;

    sort(v.begin() + 1, v.end());

    memset(dp, -1, sizeof dp);
    fout << Solve(1, n, 0) << '\n';

    return 0;

}

//Trust me, I'm the Doctor!