Problem J: Tree Construction

Consider a two-dimensional space with a set of points (xi, yi) that satisfy xi < xj and yi > yj for all i < j. We want to have them all connected by a directed tree whose edges go toward either right (x positive) or upward (y positive). The figure below shows an example tree.

<image>
Figure 1: An example tree

Write a program that finds a tree connecting all given points with the shortest total length of edges.



Input

The input begins with a line that contains an integer n (1 <= n <= 1000), the number of points. Then n lines follow. The i-th line contains two integers xi and yi (0 <= xi, yi <= 10000), which give the coordinates of the i-th point.

Output

Print the total length of edges in a line.

Examples

Input

5
1 5
2 4
3 3
4 2
5 1


Output

12


Input

1
10000 0


Output

0
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<29;
const double EPS = 1e-8;
const int MOD = 1000000007;

#define X first
#define Y second
#define MAXSIZE 1001
int n;
vector<pii> p;
int X[MAXSIZE][MAXSIZE];

int optimalBST(int n) {
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) 
      X[i][j] = i+1 == j ? 0 : INF;
    X[i][i] = 0;
  }
  for (int w = 2; w <= n; ++w) 
    for (int i = 0, j; (j = i+w) <= n; ++i) 
      for (int r = i+1; r < j; ++r) {
        int c = X[i][r] + X[r][j] + p[r-1].Y - p[j-1].Y + p[r].X - p[i].X;
        if (X[i][j] > c) X[i][j] = c;
      }
  return X[0][n];
}
int main(){
	ios::sync_with_stdio(false);
	while(cin >> n){
		p.resize(n);
		REP(i, n) cin >> p[i].X >> p[i].Y;
		cout << optimalBST(n) << endl;
	}
	return 0;
}