#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5, INF = 2e9;
int n;
arr<int, N> s, t;
map<int, int> flw;
vec<pii> mrgd;
int flw_cmp() {
for (int i = 0; i <= n; i++) {
if (s[i] <= t[i])
flw[s[i]]++, flw[t[i]]--;
else
flw[t[i]]--, flw[s[i]]++;
}
int prv = 0;
for (auto it = flw.begin(); it != flw.end(); it++) {
it->sec += prv;
prv = it->sec;
}
int ans = 0;
for (auto it = flw.begin(); next(it, 1) != flw.end(); it++) {
if (it->sec == 0) continue;
if (it->sec > 0)
ans += it->sec * (next(it, 1)->fir - it->fir);
mrgd.push_back({it->fir, next(it, 1)->fir});
}
// for (pii x : flw)
// cerr << x.fir << ": " << x.sec << '\n';
return ans;
}
struct Dsj {
map<int, int> prnt, sz;
void intl() {
for (pii x : flw) prnt[x.fir] = x.fir, sz[x.fir] = 1;
}
int pr(int u) {
return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
}
bool mrg(int u, int v) {
u = pr(u), v = pr(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
prnt[v] = u, sz[u] += sz[v];
return true;
}
} dsj;
vec<vec<int>> edg;
int mst_cmp() {
for (auto it = flw.begin(); next(it, 1) != flw.end(); it++)
edg.push_back({next(it, 1)->fir - it->fir, it->fir, next(it, 1)->fir});
sort(edg.begin(), edg.end());
dsj.intl();
for (int i = 0; i <= n; i++) dsj.mrg(s[i], t[i]);
for (pii x : mrgd) dsj.mrg(x.fir, x.sec);
int ans = 0;
for (vec<int> x : edg) {
int u = x[1], v = x[2];
if (!dsj.mrg(u, v)) continue;
// cerr << u << " " << v << '\n';
ans += x[0];
}
return ans;
}
int plan_roller_coaster(vec<signed> _s, vec<signed> _t) {
n = _s.size();
for (int i = 1; i <= n; i++) s[i] = _s[i - 1], t[i] = _t[i - 1];
s[0] = INF, t[0] = 1;
int ans = flw_cmp();
ans += mst_cmp();
return ans;
}
