#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define sz(a) (int)(a.size())
#define inf 1e17
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define problem "a"
template<typename A, typename B, typename C>
struct triple {
A X;
B Y;
C Z;
triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) {
return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) {
if (a.X != b.X)
return a.X < b.X;
if (a.Y != b.Y)
return a.Y < b.Y;
return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p) {
ofs << "( " << p.F << " , " << p.S << " )";
return ofs;
}
template<typename T>
void print(T a) {
for (auto i : a)
cout << i << ' ';
cout << '\n';
}
template<typename T>
T max(T a, T b, T c) {
return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c) {
return min(a, min(b, c));
}
template<typename T, typename D>
D min(T a) {
return *min_element(all(a));
}
template<typename T, typename D>
D max(T a) {
return *max_element(all(a));
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = sz(s);
vector<vector<ll> > dp(1 << n, vector<ll>(n, inf));
rngi(i, n) dp[1 << i][i] = 0;
rngi(mask, 1 << n) rngi(j, n)
if (dp[mask][j] != inf) rngi(k, n) if (~mask & 1 << k)
dp[mask | 1 << k][k] = min(dp[mask | 1 << k][k], dp[mask][j] + max(0, t[j] - s[k]));
long long men = min<vector<ll>, ll>(dp[(1 << n) - 1]);
s.push_back(inf); t.push_back(1);
vi tmp(s); for (auto x : t) tmp.push_back(x);
SORT(tmp); tmp.erase(unique(all(tmp)), tmp.end());
n++;
int m = sz(tmp);
rngi(i, n) {
s[i] = lower_bound(all(tmp), s[i]) - tmp.begin();
t[i] = lower_bound(all(tmp), t[i]) - tmp.begin();
}
vi tr(4 * m), tt(4 * m);
auto push = [&](int v, int l, int r) {
if (tt[v]) {
tt[v << 1] += tt[v];
tt[v << 1 | 1] += tt[v];
int m = l + r >> 1;
tr[v << 1] += (m - l + 1) * tt[v];
tr[v << 1 | 1] += (r - m) * tt[v];
tt[v] = 0;
}
};
function<int(int, int, int, int)> f = [&](int v, int l, int r, int p) {
if (l == r)return tr[v];
int m = l + r >> 1;
push(v, l, r);
if (p <= m) return f(v << 1, l, m, p);
return f(v << 1 | 1, m + 1, r, p);
};
function<void(int, int, int, int, int, int)> add = [&](int v, int l, int r, int _l, int _r, int x) {
if (r < _l || _r < l)return;
if (_l <= l && r <= _r) { tr[v] += (r - l + 1) * x; tt[v]+=x; return; }
int m = l + r >> 1;
push(v, l, r);
add(v << 1, l, m, _l, _r, x); add(v << 1 | 1, m + 1, r, _l, _r, x);
tr[v] = tr[v << 1] + tr[v << 1 | 1];
};
rngi(i, n) {
if (s[i] < t[i]) add(1, 0, m - 1, s[i], t[i] - 1, 1);
else if (s[i] > t[i]) add(1, 0, m - 1, t[i], s[i] - 1, -1);
}
vector<vi> g(m), gr(m);
rngi(i, m - 1) {
if (f(1, 0, m - 1, i) > 0) return men;
if (f(1, 0, m - 1, i) < 0) g[i].push_back(i + 1), gr[i + 1].push_back(i);
}
rngi(i, n) g[s[i]].push_back(t[i]), gr[t[i]].push_back(s[i]);
vi used(m), c(m);
vi ord; int cc = 0;
function<void(int)> dfs1 = [&](int v) {
used[v] = 1;
for (auto to : g[v]) if (!used[to]) dfs1(to);
ord.pb(v);
};
function<void(int)> dfs2 = [&](int v) {
c[v] = cc;
for (auto to : gr[v]) if (!c[to]) dfs2(to);
};
rngi(i, m) if (!used[i]) dfs1(i);
rngi(i, m) if (!c[ord[m - i - 1]]){
cc++;
dfs2(m - i - 1);
}
if(cc>1){
assert(men==0);
}
return cc > 1;
}
