#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
// Input
long long N;
long long S[1 << 18], T[1 << 18];
long long dp[1 << 16][16];
// Graph
bool used[1 << 19];
int cnt[1 << 19];
int col[1 << 19], cntv;
vector<int> ord;
vector<int> X[1 << 19];
vector<int> Y[1 << 19];
void dfs1(int pos) {
used[pos] = true;
for (int i : X[pos]) {
if (used[i] == true) continue;
dfs1(i);
}
ord.push_back(pos);
}
void dfs2(int pos) {
col[pos] = cntv;
for (int i : Y[pos]) {
if (col[i] >= 1) continue;
dfs2(i);
}
}
long long solve_subtask3() {
// ZAATS
vector<long long> vec;
vec.push_back(0);
vec.push_back(1000000007);
for (int i = 0; i < N; i++) vec.push_back(S[i]);
for (int i = 0; i < N; i++) vec.push_back(T[i]);
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 0; i < N; i++) S[i] = lower_bound(vec.begin(), vec.end(), S[i]) - vec.begin();
for (int i = 0; i < N; i++) T[i] = lower_bound(vec.begin(), vec.end(), T[i]) - vec.begin();
// GRAPH
cnt[0] += 1;
cnt[vec.size() - 1] -= 1;
X[vec.size() - 1].push_back(0);
Y[0].push_back(vec.size() - 1);
for (int i = 0; i < N; i++) X[S[i]].push_back(T[i]);
for (int i = 0; i < N; i++) Y[T[i]].push_back(S[i]);
for (int i = 0; i < N; i++) cnt[S[i]] -= 1;
for (int i = 0; i < N; i++) cnt[T[i]] += 1;
// HANTE
for (int i = 1; i < (int)vec.size(); i++) cnt[i] += cnt[i - 1];
for (int i = 0; i < (int)vec.size(); i++) {
if (cnt[i] <= -1) return 1000000007;
if (cnt[i] >= 1) { X[i].push_back(i + 1); Y[i + 1].push_back(i); }
}
// SCC
for (int i = 0; i < (int)vec.size(); i++) {
if (used[i] == true) continue;
dfs1(i);
}
for (int i = ord.size() - 1; i >= 0; i--) {
if (col[ord[i]] >= 1) continue;
cntv++;
dfs2(ord[i]);
}
// FINAL
if (cntv == 1) return 0;
return 1000000007;
}
long long solve_subtask2() {
// PRCLC
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) dp[i][j] = (1LL << 60);
}
for (int i = 0; i < N; i++) dp[1 << i][i] = 0;
// CALC
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
if (dp[i][j] == (1LL << 60)) continue;
for (int k = 0; k < N; k++) {
if ((i / (1 << k)) % 2 == 1) continue;
long long cost = max(0LL, T[j] - S[k]);
dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + cost);
}
}
}
// FINAL
long long Answer = (1LL << 60);
for (int i = 0; i < N; i++) Answer = min(Answer, dp[(1 << N) - 1][i]);
return Answer;
}
int cnts = 0;
long long plan_roller_coaster(vector<int> s, vector<int> t) {
N = s.size();
for (int i = 0; i < N; i++) S[i] = s[i];
for (int i = 0; i < N; i++) T[i] = t[i];
cnts += 1;
if (N <= 16) return solve_subtask2();
return solve_subtask3();
}
