#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "railroad.h"
namespace TEST2 {
const int MAXN = 16;
ll dp[1<<MAXN][MAXN];
ll solve(VI a, VI b) {
int n = a.size();
rep(s, 1<<n) rep(i, n) if (s & (1<<i)) {
int st = (s^(1<<i));
if (st == 0) {
dp[s][i] = 0;
} else {
dp[s][i] = 1e18;
rep(j, n) if (st & (1<<j)) {
setmin(dp[s][i], dp[st][j] + max(0, b[j]-a[i]));
}
}
}
ll ans = 1e18;
rep(i, n) setmin(ans, dp[(1<<n)-1][i]);
return ans;
}
};
struct DSU {
VI par;
VI cnt;
DSU(int n) {
par = cnt = VI(n);
rep(i, n) {
par[i] = i;
cnt[i] = 1;
}
}
int get(int u) {
if (u == par[u]) return u;
return par[u] = get(par[u]);
}
bool join(int u, int v) {
u = get(u);
v = get(v);
if (u == v) return false;
if (cnt[v] > cnt[u]) swap(u, v);
cnt[u] += cnt[v];
par[v] = u;
return true;
}
};
namespace TEST3 {
int n;
VVI gp;
VVI trans;
ll solve(VI U, VI V) {
VI val;
{/* compress */
map<int, int> ind;
rep(i, U.size()) ind[U[i]] = ind[V[i]] = 0;
n = 0;
for (auto& p : ind) {
p.ss = n++;
val.pb(p.ff);
}
rep(i, U.size()) {
U[i] = ind[U[i]];
V[i] = ind[V[i]];
}
}
if (n == 1) return 0;
gp = trans = VVI(n);
rep(i, U.size()) {
gp[U[i]].pb(V[i]);
trans[V[i]].pb(U[i]);
}
gp[n-1].pb(0);
trans[0].pb(n-1);
VI extradown(n);
VI extraup(n);
ll ans = 0;
{/* add edges to make graph eulerian */
VI a(n);
rep(u, n) a[u] = gp[u].size() - trans[u].size();
stack<int> pos;
stack<int> neg;
rep(u, n) {
int cnt = abs(a[u]);
if (a[u] < 0) {
while (cnt && pos.size()) {
ans += val[u] - val[pos.top()];
/*cout << u << " " << pos.top() << endl;*/
extraup[pos.top()]++;
extraup[u]--;
pos.pop();
cnt--;
}
while (cnt--) {
neg.push(u);
}
} else if (a[u] > 0) {
while (cnt && neg.size()) {
/*cout << neg.top() << " " << u << endl;*/
extradown[neg.top()]++;
extradown[u]--;
neg.pop();
cnt--;
}
while (cnt--) {
pos.push(u);
}
}
}
}
replr(i, 1, n) {
extradown[i] += extradown[i-1];
extraup[i] += extraup[i-1];
}
rep(i, n-1) {
if (extraup[i]) {
gp[i].pb(i+1);
trans[i+1].pb(i);
/*cout << "DECOMPOSED: " << i << " " << i+1 << endl;*/
}
if (extradown[i]) {
gp[i+1].pb(i);
trans[i].pb(i+1);
/*cout << "DECOMPOSED: " << i+1 << " " << i << endl;*/
}
}
DSU dsu(n);
rep(u, n) for (int v : gp[u]) {
dsu.join(u, v);
}
VPI edges;
rep(i, n-1) edges.pb({val[i+1]-val[i], i});
sort(all(edges));
for (auto[w, u] : edges) {
if (dsu.join(u, u+1)) {
ans += w;
}
}
return ans;
}
};
ll plan_roller_coaster(VI a, VI b) {
if (a.size() <= 16) return TEST2::solve(a, b);
return TEST3::solve(a, b);
srand(time(0));
int t = 1000;
int n = 10;
int m = 4*n;
while (t--) {
cout << "counter: " << t << endl;
a = b = VI(n);
rep(i, n) {
a[i] = rand()%m+1;
b[i] = rand()%m+1;
}
if (TEST2::solve(a, b) != TEST3::solve(a, b)) {
cout << "VERJAPES" << endl;
rep(i, n) {
cout << a[i] << " " << b[i] << endl;
}
cout << "asnwers: " << TEST2::solve(a, b) << " " << TEST3::solve(a, b) << endl;
return 0;
}
}
return 0;
}
