#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;
}
};
namespace TEST3 {
int n;
VVI gp;
VVI trans;
VI vis;
void dfs(int u) {
vis[u] = true;
for (int v : gp[u]) if (!vis[v]) dfs(v);
for (int v : trans[u]) if (!vis[v]) dfs(v);
}
ll solve(VI U, VI V) {
{/* 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++;
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 extra(n);
{/* filter non-eulerian graphs */
VI a(n);
rep(u, n) a[u] = gp[u].size() - trans[u].size();
stack<int> st;
rep(u, n) {
int cnt = abs(a[u]);
if (a[u] < 0) {
while (cnt--) st.push(u);
} else if (a[u] > 0) {
while (cnt--) {
if (st.size() == 0) return 1;
/*cout << "LONG EDGE: " << st.top() << " " << u << endl;*/
extra[st.top()]++;
extra[u]--;
st.pop();
}
}
}
if (st.size()) return 1;
}
replr(i, 1, n) extra[i] += extra[i-1];
rep(i, n-1) if (extra[i]) {
gp[i].pb(i+1);
trans[i+1].pb(i);
/*cout << "DECOMPOSED: " << i << " " << i+1 << endl;*/
}
vis = VI(n);
dfs(0);
rep(u, n) if (!vis[u]) return 2;
return 0;
}
};
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 = 10000;
int n = 10;
int m = 2*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 ((bool)TEST2::solve(a, b) != (bool)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;
}
