#include "railroad.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
const int MAXN = 200055;
int ud[MAXN*2], C[MAXN*2], O[MAXN*2];
vector<int> XV;
int A[MAXN], B[MAXN], AI[MAXN], BI[MAXN];
ll Ans;
int N, K;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
ll getAns() {
XV.eb(0); XV.eb(INF);
for(int i = 0; i < N; i++) {
XV.eb(A[i]);
XV.eb(B[i]);
}
sorv(XV); univ(XV); K = sz(XV);
iota(ud, ud+K, 0);
for(int i = 0; i < N; i++) {
AI[i] = int(lower_bound(allv(XV), A[i]) - XV.begin());
BI[i] = int(lower_bound(allv(XV), B[i]) - XV.begin());
C[AI[i]]--; C[BI[i]]++;
uf(AI[i], BI[i]);
}
C[0] = -1; C[1]++; uf(0, 1);
for(int i = 2; i < K; i++) if(C[i-1]) {
uf(i-1, i);
if(C[i-1] < 0) Ans -= ll(C[i-1]) * (XV[i]-XV[i-1]);
C[i] += C[i-1]; C[i-1] = 0;
}
iota(O, O+K, 0); sort(O+1, O+K, [&](int a, int b) {
return XV[a]-XV[a-1] < XV[b]-XV[b-1];
});
for(int oi = 1, i; oi < K; oi++) {
i = O[oi];
if(uf(i-1) == uf(i)) continue;
Ans += XV[i] - XV[i-1];
uf(i-1, i);
}
return Ans;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
::N = sz(s);
for(int i = 0; i < N; i++) {
::A[i] = s[i];
::B[i] = t[i];
}
return getAns();
}
