#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second
struct DSU {
vector<int> p,sz;
DSU(int n) {
forn(i,n) p.pb(i), sz.pb(1);
}
int get(int u) {
return p[u]==u?u:get(p[u]);
}
void uni(int u, int v) {
u=get(u),v=get(v);
if (u==v) return;
if (sz[u]<sz[v]) swap(u,v);
sz[u]+=sz[v];
p[v]=u;
}
};
ll dp[1<<16][20];
bool foo(int a, int b) {
return __builtin_popcount(a) < __builtin_popcount(b);
}
ll scuza(vector<int> s, vector<int> t) {
int n=s.size();
s.pb(-1); t.pb(0);
vector<int> b;
forn(i,1<<n) b.pb(i);
sort(all(b),foo);
forn(i,n+1) forn(j,1<<n) dp[j][i]=1e18;
dp[0][n]=0;
for(auto&m:b) {
forn(i,n+1) {
if (m) if (!(m&(1<<i))) continue;
forn(j,n) {
if (m&(1<<j)) continue;
dp[m|(1<<j)][j]=min(dp[m|(1<<j)][j],dp[m][i] + max(t[i]-s[j],0));
}
}
}
ll ans=1e18;
forn(i,n) ans=min(ans,dp[(1<<n)-1][i]);
return ans;
}
ll plan_roller_coaster(vector<int> s, vector<int> t) {
int n=s.size();
if (n<=16) return scuza(s,t);
s.pb(1e9+7);
t.pb(-1);
++n;
int m=0;
set<int> st; forn(i,n) st.insert(s[i]), st.insert(t[i]);
map<int,int> c;
for(auto&x:st) c[x]=m++;
vector<int> pr(m);
forn(i,n) s[i]=c[s[i]], t[i]=c[t[i]];
DSU dsu(m);
forn(i,n) {
pr[t[i]]++;
pr[s[i]]--;
dsu.uni(s[i],t[i]);
}
for(int i=1; i<m; ++i) pr[i]+=pr[i-1];
forn(i,m) {
if (pr[i]<0) return 1;
if (pr[i]>0) dsu.uni(i,i+1);
}
int ans=1;
forn(i,n) ans&=dsu.get(i)==dsu.get(0);
return !ans;
}
