Problem: Annie has gotten bored of winning every coding contest and farming unlimited rating. Today, she is going to farm potatoes instead.

Annie's garden is an infinite 2D plane. She has n potatoes to plant, and the i-th potato must be planted at (x_i,y_i). Starting at the point (0, 0), Annie begins walking, in one step she can travel one unit right or up (increasing her x or y coordinate by 1 respectively). At any point (X,Y) during her walk she can plant some potatoes at arbitrary points using her potato gun, consuming max(|X-x|,|Y-y|) units of energy in order to plant a potato at (x,y). Find the minimum total energy required to plant every potato.

Note that Annie may plant any number of potatoes from any point.

Input

The first line contains the integer n (1 ≤ n ≤ 800 000).

The next n lines contain two integers x_i and y_i (0 ≤ x_i,y_i ≤ 10^9), representing the location of the i-th potato. It is possible that some potatoes should be planted in the same location.

Output

Print the minimum total energy to plant all potatoes.

Examples

Input


2
1 1
2 2


Output


0


Input


2
1 1
2 0


Output


1


Input


3
5 5
7 7
4 9


Output


2


Input


10
5 1
4 0
9 6
0 2
10 1
9 10
3 10
0 10
8 9
1 5


Output


19


Input


10
1 1
2 2
2 0
4 2
4 0
2 0
0 2
4 0
4 2
5 1


Output


6

Note

In example 1, Annie can travel to each spot directly and plant a potato with no energy required.

In example 2, moving to (1,0), Annie plants the second potato using 1 energy. Next, she travels to (1,1) and plants the first potato with 0 energy.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define range(i, n) for (int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ar array
using namespace std;

// using namespace __gnu_pbds;
/*
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
*/

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int INFi = 2e9 + 5;
const int maxN = 4e5 + 5;
const int md = 1e9 + 7;
const ll INF = 2e18;

double getTime() { return clock() / (double) CLOCKS_PER_SEC; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap {
    int y{};
    int xs{};
    int x{};
    int p{};
    int addp{};
    //int sz{};

    Treap *l = nullptr, *r = nullptr;

    Treap(int _x, int _p = 0) : y(rng()), xs(_x), p(_p), addp(0), x(_x) {}
};

int get_xs(Treap *a) {
    if (!a) return 0;
    return a->xs;
}

void upd(Treap *a) {
    if (!a) return;
    a->xs = a->x + get_xs(a->l) + get_xs(a->r);
}

void check(Treap *a, int x) {
    if (!a) return;
    a->addp += x;
    a->p += x;
}

void push(Treap *a) {
    if (!a || !a->addp) return;
    check(a->l, a->addp);
    check(a->r, a->addp);
    a->addp = 0;
}

typedef pair<Treap *, Treap *> ptt;

Treap *merge(Treap *a, Treap *b) {
    if (!a) return b;
    if (!b) return a;
    if (a->y > b->y) {
        push(a);
        a->r = merge(a->r, b);
        upd(a);
        return a;
    } else {
        push(b);
        b->l = merge(a, b->l);
        upd(b);
        return b;
    }
}

// Try : [0, x]
ptt split1(Treap *a, int x) {
    if (!a) return {nullptr, nullptr};
    push(a);
    if (get_xs(a->l) + a->x <= x) {
        auto[b, c] = split1(a->r, x - get_xs(a->l) - a->x);
        a->r = b;
        upd(a);
        return {a, c};
    } else {
        auto[b, c] = split1(a->l, x);
        a->l = c;
        upd(a);
        return {b, a};
    }
}


ptt split2(Treap *a, int x) {
    if (!a) return {nullptr, nullptr};
    push(a);
    if (get_xs(a->l) < x) {
        auto[b, c] = split2(a->r, x - get_xs(a->l) - a->x);
        a->r = b;
        upd(a);
        return {a, c};
    } else {
        auto[b, c] = split2(a->l, x);
        a->l = c;
        upd(a);
        return {b, a};
    }
}

ptt splitP(Treap *a, int p) {
    if (!a) return {nullptr, nullptr};
    push(a);
    if (a->p < p) {
        auto[b, c] = splitP(a->r, p);
        a->r = b;
        upd(a);
        return {a, c};
    } else {
        auto[b, c] = splitP(a->l, p);
        a->l = c;
        upd(a);
        return {b, a};
    }
}

ll ans = 0;
void dfs(Treap *t) {
    if (!t) return;
    push(t);
    dfs(t->l);
    if (t->p < 0) {
        ans += 1ll * t->p * t->x;
    }
    dfs(t->r);
}

void solve() {
    int n; cin >> n;
    vector<int> x(n), y(n);
    range(i, n) cin >> x[i] >> y[i];
    Treap * root = new Treap(1);
    int last = 0;
    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&] (const int &i, const int &j) {
        return x[i] + y[i] < x[j] + y[j];
    });
    for(auto &i : ord) {
        int cur = x[i] + y[i];
        if (cur != last) {
            auto[L, r2] = splitP(root, 0);
            auto[mid, R] = splitP(r2, 1);
            if (!mid) {
                mid = new Treap(0);
            }
            mid->xs += (cur - last);
            mid->x += (cur - last);
            last = cur;
            root = merge(merge(L, mid), R);
        }
        ans += x[i];
        {
            auto[L, r2] = split1(root, x[i]);
            auto[mid, R] = split2(r2, x[i] - get_xs(L));
            if (mid) {
                int len = mid->x;
                assert(get_xs(L) < x[i]);
                assert(get_xs(L) + len > x[i]);
                int lenL = x[i] - get_xs(L);
                int lenR = len - lenL;
                Treap * mid2 = new Treap(lenR, mid->p);
                mid->x = mid->xs = lenL;
                L = merge(L, mid);
                R = merge(mid2, R);
            }
            check(L, -1);
            check(R, 1);
            root = merge(L, R);
        }
    }
    dfs(root);
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int tests = 1;
    //cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}