#include "railroad.h"
#include <iostream>
#include <assert.h>
#include <queue>
#include <utility>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
int N;
ll ans=1e18;
ll S[1000006],T[1000006];
ll DP[1000006][20];
priority_queue<pll> PQS,PQT;
bool V[1000006];
ll F(int b, int i){
assert(b&(1<<i));
if(DP[b][i]!=-1)
return DP[b][i];
b=b^(1<<i);
if(!b)
return 0;
ll res=1e18;
for(int j=0;j<N;j++)
if(b&(1<<j) and j!=i)
res=min(res,F(b,j)+max(0LL,T[j]-S[i]));
DP[b|(1<<i)][i]=res;
return res;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
N=s.size();
for(int i=0;i<N;i++)
S[i]=s[i];
for(int i=0;i<N;i++)
T[i]=t[i];
if(N>16){
for(int i=0;i<N;i++){
PQS.push({S[i],i});
PQT.push({T[i],i});
}
S[N]=1e18;
T[N]=-1;
PQS.push({S[N],N});
PQT.push({T[N],N});
int cont=N+1,x,y;
while(PQS.size() and PQT.size()){
while(V[PQS.top().second] and PQS.size())
PQS.pop();
while(V[PQT.top().second] and PQT.size())
PQT.pop();
if(PQS.empty() and PQT.empty())
return 0;
x=PQT.top().second;
y=PQS.top().second;
if(x==y)
V[x]=true;
else if(T[x]<=S[y]){
V[x]=true;
V[y]=true;
S[cont]=S[x];
T[cont]=T[y];
PQS.push({S[cont],cont});
PQT.push({T[cont],cont});
cont++;
}
else
return 1;
}
return 0;
}
int b=(1<<N)-1;
for(int i=0;i<N;i++)
for(int j=0;j<=b;j++)
DP[j][i]=-1;
for(int i=0;i<N;i++)
ans=min(ans,F(b,i));
return ans;
}
/*
4
1 3
3 7
10 10
20 2
*/
