#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using Edge = pair<ll, pll>;
#define fi first
#define se second
const ll maxN = 17;
const ll INF = 1e18;
ll n;
vector<ll> compress;
vector<ll> cs, ct;
struct DSU {
vector<ll> par, sz;
DSU(ll n) {
par = sz = vector<ll>(n+1, 1);
iota(par.begin(), par.end(), 0);
}
ll rep(ll x) {
return ((x == par[x]) ? (x) : (par[x] = rep(par[x])));
}
bool check(ll x, ll y) {
return (rep(x) == rep(y));
}
void join(ll x, ll y) {
ll a = rep(x), b = rep(y);
if (a == b) return;
if (sz[a] < sz[b]) {swap(a, b);}
par[b] = a;
sz[a] += sz[b];
}
};
ll plan_roller_coaster(vector<int> s, vector<int> t) {
n = s.size();
for (auto i : s) {compress.push_back(i);}
for (auto i : t) {compress.push_back(i);}
compress.push_back(0);
compress.push_back(INF);
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(), compress.end()), compress.end());
for (auto i : s) {
cs.push_back(lower_bound(compress.begin(), compress.end(), i) - compress.begin());
}
for (auto i : t) {
ct.push_back(lower_bound(compress.begin(), compress.end(), i) - compress.begin());
}
ll CS = compress.size();
DSU D = DSU(CS);
//for (auto i : compress) cout << i << ' '; cout << '\n';
// edges for MST
vector<Edge> edges;
for (ll i = 1; i < compress.size(); i++) {
edges.push_back({compress[i] - compress[i-1], {i-1, i}});
}
vector<ll> lines(CS, 0);
// right line = 1, left line = -1
for (ll i = 0; i < n; i++) {
D.join(cs[i], ct[i]);
//cout << i << ' ' << cs[i] << ' ' << ct[i] << '\n';
if (s[i] < t[i]) {
// right line
lines[cs[i]]++;
lines[ct[i]]--;
} else {
// left line
lines[ct[i]]--;
lines[cs[i]]++;
}
}
lines[0]--;
//for (auto i : lines) cout << i << ' '; cout << '\n';
ll run = 0, ans = 0;
for (ll i = 0; i < CS-1; i++) {
run += lines[i];
//cout << run << ' ';
if (run > 0) {
// more right lines than left lines
ans += 1ll * run * (compress[i+1] - compress[i]);
D.join(i, i+1);
} else if (run < 0) {
// more left lines than right lines
D.join(i, i+1);
}
}
//cout << '\n';
// make the graph connected via Kruskal
sort(edges.begin(), edges.end());
for (auto &[w, p] : edges) {
if (D.check(p.fi, p.se)) continue;
ans += compress[p.se] - compress[p.fi];
D.join(p.fi, p.se);
}
return ans;
}
#ifdef Zanite
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> s(n), t(n);
for (int i = 0; i < n; ++i)
assert(2 == scanf("%d%d", &s[i], &t[i]));
long long ans = plan_roller_coaster(s, t);
printf("%lld\n", ans);
return 0;
}
#endif
