#include<bits/stdc++.h>
#define INF 1LL<<60
#define x first
#define y second
using namespace std;
ifstream f("wanted.in");
ofstream g("wanted.out");
int i,n;
pair<int,int>a[203];
long long d[204][204][2];
inline long long dei(int li,int ls,int t)
{
    int s=(t<li);
    if(li>ls) return 0;
    if(d[li][ls][s]<INF&&d[li][ls][s]) return d[li][ls][s];
    d[li][ls][s]=INF;
    for(int i=li;i<=ls;++i)
        d[li][ls][s]=min(max(dei(li,i-1,i),dei(i+1,ls,i))+a[i].y+a[t].y+abs(a[i].x-a[t].x),d[li][ls][s]);
    return d[li][ls][s];
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    g<<dei(1,n,0);
    return 0;
}