#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T, typename V>
void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }
template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template <typename T> vector<T> sort_unique(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <typename T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <typename T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T, size_t sz> ostream &operator<<(ostream &os, const array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
#if __cplusplus >= 201703L
template <typename... T> istream &operator>>(istream &is, tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <typename... T> ostream &operator<<(ostream &os, const tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
#endif
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T, typename TH> ostream &operator<<(ostream &os, const unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <typename TK, typename TV, typename TH> ostream &operator<<(ostream &os, const unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl
#define dbgif(cond, x) ((cond) ? cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl : cerr)
#else
#define dbg(x) (x)
#define dbgif(cond, x) 0
#endif

// Slope trick: fast operations for convex piecewise-linear functions
//
// Implementation idea:
// - https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
// - https://ei1333.github.io/library/structure/others/slope-trick.cpp
template <class T, T INF = std::numeric_limits<T>::max() / 2>
class slope_trick {
    T min_f;
    T displacement_l, displacement_r;
    std::priority_queue<T, std::vector<T>, std::less<T>> L;
    std::priority_queue<T, std::vector<T>, std::greater<T>> R;
    void pushR(const T &a) { R.push(a - displacement_r); }
    T topR() const { return R.empty() ? INF : R.top() + displacement_r; }
    T popR() {
        auto ret = topR();
        if (R.size()) R.pop();
        return ret;
    }
    void pushL(const T &a) { L.push(a + displacement_l); }
    T topL() const { return L.empty() ? -INF : L.top() - displacement_l; }
    T popL() {
        auto ret = topL();
        if (L.size()) L.pop();
        return ret;
    }

public:
    slope_trick() : min_f(0), displacement_l(0), displacement_r(0) { static_assert(INF > 0); }
    // argmin f(x), min f(x)
    using Q = struct { T min, lo, hi; };
    Q get_min() const { return {min_f, topL(), topR()}; }
    // f(x) += b
    void add_const(const T &b) { min_f += b; }
    // f(x) += max(x - a, 0)  _/
    void add_relu(const T &a) { min_f += std::max(T(0), topL() - a), pushL(a), pushR(popL()); }
    // f(x) += max(a - x, 0)  \_
    void add_irelu(const T &a) { min_f += std::max(T(0), a - topR()), pushR(a), pushL(popR()); }
    // f(x) += |x - a|  \/
    void add_abs(const T &a) { add_relu(a), add_irelu(a); }
    // f(x) <- min_{0 <= y <= w} f(x + y)  .\ -> \_
    void move_left_curve(const T &w) { displacement_l += w; }
    // f(x) <- min_{0 <= y <= w} f(x - y)  /. -> _/
    void move_right_curve(const T &w) { displacement_r += w; }
    // f(x) <- f(x + dx) \/. -> .\/
    void translate(const T &dx) { move_left_curve(-dx), move_right_curve(dx); }
    // return f(x)
    T get_destructive(const T &x) {
        T ret = get_min();
        while (L.size()) ret += std::max(T(0), popL() - x);
        while (R.size()) ret += std::max(T(0), x - popR());
        return ret;
    }
};

int main() {
    int N;
    cin >> N;
    vector<plint> sumy(N);
    for (auto &[x, y] : sumy) cin >> x >> y, x += y;
    sort(sumy.begin(), sumy.end());
    lint now = 0;

    slope_trick<long long> dp;
    lint origin = 0;
    for (auto [sum, y] : sumy) {
        const lint dt = sum - now;
        now = sum;
        dp.move_right_curve(dt);
        dp.add_abs(y);
    }
    cout << dp.get_min().min << endl;
}

### Prompt

Develop a solution in cpp to the problem described below:

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.

### Response

```cpp
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T, typename V>
void ndarray(vector<T>& vec, const V& val, int len) { vec.assign(len, val); }
template <typename T, typename V, typename... Args> void ndarray(vector<T>& vec, const V& val, int len, Args... args) { vec.resize(len), for_each(begin(vec), end(vec), [&](T& v) { ndarray(v, val, args...); }); }
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template <typename T> vector<T> sort_unique(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <typename T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <typename T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T, size_t sz> ostream &operator<<(ostream &os, const array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
#if __cplusplus >= 201703L
template <typename... T> istream &operator>>(istream &is, tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <typename... T> ostream &operator<<(ostream &os, const tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
#endif
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T, typename TH> ostream &operator<<(ostream &os, const unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << '(' << pa.first << ',' << pa.second << ')'; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <typename TK, typename TV, typename TH> ostream &operator<<(ostream &os, const unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl
#define dbgif(cond, x) ((cond) ? cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl : cerr)
#else
#define dbg(x) (x)
#define dbgif(cond, x) 0
#endif

// Slope trick: fast operations for convex piecewise-linear functions
//
// Implementation idea:
// - https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
// - https://ei1333.github.io/library/structure/others/slope-trick.cpp
template <class T, T INF = std::numeric_limits<T>::max() / 2>
class slope_trick {
    T min_f;
    T displacement_l, displacement_r;
    std::priority_queue<T, std::vector<T>, std::less<T>> L;
    std::priority_queue<T, std::vector<T>, std::greater<T>> R;
    void pushR(const T &a) { R.push(a - displacement_r); }
    T topR() const { return R.empty() ? INF : R.top() + displacement_r; }
    T popR() {
        auto ret = topR();
        if (R.size()) R.pop();
        return ret;
    }
    void pushL(const T &a) { L.push(a + displacement_l); }
    T topL() const { return L.empty() ? -INF : L.top() - displacement_l; }
    T popL() {
        auto ret = topL();
        if (L.size()) L.pop();
        return ret;
    }

public:
    slope_trick() : min_f(0), displacement_l(0), displacement_r(0) { static_assert(INF > 0); }
    // argmin f(x), min f(x)
    using Q = struct { T min, lo, hi; };
    Q get_min() const { return {min_f, topL(), topR()}; }
    // f(x) += b
    void add_const(const T &b) { min_f += b; }
    // f(x) += max(x - a, 0)  _/
    void add_relu(const T &a) { min_f += std::max(T(0), topL() - a), pushL(a), pushR(popL()); }
    // f(x) += max(a - x, 0)  \_
    void add_irelu(const T &a) { min_f += std::max(T(0), a - topR()), pushR(a), pushL(popR()); }
    // f(x) += |x - a|  \/
    void add_abs(const T &a) { add_relu(a), add_irelu(a); }
    // f(x) <- min_{0 <= y <= w} f(x + y)  .\ -> \_
    void move_left_curve(const T &w) { displacement_l += w; }
    // f(x) <- min_{0 <= y <= w} f(x - y)  /. -> _/
    void move_right_curve(const T &w) { displacement_r += w; }
    // f(x) <- f(x + dx) \/. -> .\/
    void translate(const T &dx) { move_left_curve(-dx), move_right_curve(dx); }
    // return f(x)
    T get_destructive(const T &x) {
        T ret = get_min();
        while (L.size()) ret += std::max(T(0), popL() - x);
        while (R.size()) ret += std::max(T(0), x - popR());
        return ret;
    }
};

int main() {
    int N;
    cin >> N;
    vector<plint> sumy(N);
    for (auto &[x, y] : sumy) cin >> x >> y, x += y;
    sort(sumy.begin(), sumy.end());
    lint now = 0;

    slope_trick<long long> dp;
    lint origin = 0;
    for (auto [sum, y] : sumy) {
        const lint dt = sum - now;
        now = sum;
        dp.move_right_curve(dt);
        dp.add_abs(y);
    }
    cout << dp.get_min().min << endl;
}

```