#include "railroad.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const ll B=1e15;
ll dp[1<<16][16];
vector<int>s,t;
int n,all;
ll rec(int mask,int last){
if(mask==all)
return 0;
ll &ret=dp[mask][last];
if(~ret)return ret;ret=B;
for(int i=0;i<n;i++)
if(!(mask>>i&1))
umin(ret,rec(mask|(1<<i),i)+max(0,t[last]-s[i]));
return ret;
}
vector<int>adj[MAXN];
int in[MAXN],fup[MAXN],tin[MAXN],par[MAXN],TIM,S;
stack<int>st;
void dfs(int nd){
tin[nd]=fup[nd]=++TIM;
st.push(nd);in[nd]=1;
tr(it,adj[nd]){
if(!tin[*it]){
dfs(*it);
umin(fup[nd],fup[*it]);
}
else if(in[*it])
umin(fup[nd],tin[*it]);
}
if(fup[nd]==tin[nd]){
int aux;S++;
do{
aux=st.top();st.pop();in[aux]=0;
}while(aux!=nd);
}
}
long long plan_roller_coaster(vector<int> si, vector<int> ti) {
s=si;t=ti;
n = (int) s.size();
if(n<=16){
memset(dp,-1,sizeof dp);
all=(1<<n)-1;
ll ans=B;
for(int i=0;i<n;i++)
umin(ans,rec((1<<i),i));
return ans;
}
vector<int>v;v.pb(1);
for(int i=0;i<n;i++)
v.pb(s[i]),v.pb(t[i]);
sort(all(v));v.erase(unique(all(v)),v.end());
for(int i=0;i<n;i++){
s[i]=lower_bound(all(v),s[i])-v.begin();
t[i]=lower_bound(all(v),t[i])-v.begin();
s[i]++;t[i]++;
if(s[i]<t[i])
par[s[i]]++,par[t[i]]--;
if(s[i]>t[i])
par[t[i]]--,par[s[i]]++;
adj[s[i]].pb(t[i]);
}n=int(v.size());
adj[n].pb(1);
par[1]--;int sum=0;
for(int i=1;i<n;i++){
sum+=par[i];
if(sum>0)
return 1;
if(sum<0)
adj[i].pb(i+1);
}
int cc=0;
for(int i=1;i<=n;i++)
if(!tin[i]){
dfs(i);cc++;
if(cc>1)return 1;
}
return (S!=1);
}
