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 <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 1e5+5;

int n;
int l[N], r[N];
long ans, lz_l, lz_r;
multiset<long> L, R;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d", l+i, r+i), r[i] -= l[i];
    for(int i = 1; i <= n; i++) {
        ans += l[i];
        L.emplace(l[i] + lz_l), R.emplace(l[i] - lz_r);
        while(*L.rbegin() - lz_l > *R.begin() + lz_r) {
            long l = *L.rbegin(), r = *R.begin();
            L.erase(L.find(l)), R.erase(R.find(r));
            L.emplace(r + lz_r + lz_l), R.emplace(l - lz_l - lz_r);
        }
        long pv = 0;
        while(!L.empty() && *L.begin() - lz_l - r[i+1] <= 0) {
            ans -= abs(*L.begin() - lz_l - pv) * L.size();
            pv = *L.begin() - lz_l;
            L.erase(L.begin());
        }
        ans -= abs(pv - r[i+1]) * L.size();
        lz_l += r[i+1], lz_r += r[i];
    }
    long m = L.size(), pv = 0;
    for(long x : L) {
        ans -= abs(x - lz_l - pv) * m--;
        pv = x - lz_l;
    }
    printf("%lld\n", ans);

    return 0;
}