AtCoDeer the deer found N rectangle lying on the table, each with height 1. If we consider the surface of the desk as a two-dimensional plane, the i-th rectangle i(1≤i≤N) covers the vertical range of [i-1,i] and the horizontal range of [l_i,r_i], as shown in the following figure:

<image>

AtCoDeer will move these rectangles horizontally so that all the rectangles are connected. For each rectangle, the cost to move it horizontally by a distance of x, is x. Find the minimum cost to achieve connectivity. It can be proved that this value is always an integer under the constraints of the problem.

Constraints

* All input values are integers.
* 1≤N≤10^5
* 1≤l_i<r_i≤10^9

Input

The input is given from Standard Input in the following format:


N
l_1 r_1
l_2 r_2
:
l_N r_N


Output

Print the minimum cost to achieve connectivity.

Examples

Input

3
1 3
5 7
1 3


Output

2


Input

3
2 5
4 6
1 4


Output

0


Input

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000


Output

1999999680


Input

5
123456 789012
123 456
12 345678901
123456 789012
1 23


Output

246433


Input

1
1 400


Output

0
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PPI;
typedef pair<ll,P> PIP;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define PQ2(T) priority_queue<T>
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define REP(i,a,b) for(ll (i)=a;(i)<(ll)(b);++(i))
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) ((x)=min((x),(y)))
#define chmax(x,y) ((x)=max((x),(y)))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
#define DEBUG(x) cerr<<"line ("<<__LINE__<<")  "<<#x<<": "<<x<<endl;
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);

#define N 100010
ll l[N], r[N];
multiset<ll> ls, rs;
ll lo, ro;
ll n;

int main(){
	INIT;
	cin>>n;
	rep(i, n) cin>>l[i]>>r[i];
	ls.insert(l[0]);
	rs.insert(r[0]);
	ll res = 0;
	REP(i, 1, n){
		lo -= r[i]-l[i];
		auto itl = ls.end(); --itl;
		auto itr = rs.begin();
		if(l[i]<*itl+lo){
			ll x = *itl+lo;
			res += abs(l[i]-x);
			ls.erase(itl);
			rs.insert(x-ro);
			ls.insert(l[i]-lo);
			ls.insert(l[i]-lo);
		} else if(l[i]>*itr+ro){
			ll x = *itr+ro;
			res += abs(l[i]-x);
			rs.erase(itr);
			ls.insert(x-lo);
			rs.insert(l[i]-ro);
			rs.insert(l[i]-ro);
		} else {
			ls.insert(l[i]-lo);
			rs.insert(l[i]-ro);
		}
		/*
		{
			cerr<<"ls"<<endl;
			for(auto x: ls) cerr<<x+lo<<" "; cerr<<endl;
			cerr<<"rs"<<endl;
			for(auto x: rs) cerr<<x+ro<<" "; cerr<<endl;
		}
		*/
		itl = ls.end(); --itl;
		//cerr<<l[i]<<" "<<*itl+lo<<" "<<lo<<endl;
		//res += abs(l[i]-(*itl+lo));
		ro += r[i]-l[i];
	}
	cout<<res<<endl;
	return 0;
}
