#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> dp;
ll ans(ll state, int ind, int n, vector<int> &s, vector<int> &t){
//state -- used indices
//ind -- last used (so can take anything with s value >= t[i]
/*for (int i = 0; i<n; i++){
cout<<bool((1<<i)&state)<<' ';
}*/
//cout<<' '<<ind<<'\n';
if (state==(1<<n)-1){
return 0;
}
if (dp[state][ind]!=-1){return dp[state][ind];}
ll minv = 1e18;
for (int i = 0; i<n; i++){
if ((1<<i)&state){continue;}
//cost from ind to i
ll cost = max(t[ind]-s[i],0);
minv = min(minv,cost+ans(state+(1<<i),i,n,s,t));
}
return dp[state][ind]=minv;
}
ll subtask2(vector<int> &s, vector<int> &t){
int n = s.size();
dp.resize((1<<n),vector<ll>(n,-1));
ll minv = 1e18;
for (int i = 0; i<n; i++){
minv=min(minv,ans((1<<i),i,n,s,t));
}
return minv;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = (int) s.size();
/*if (n<=16){
return subtask2(s,t);
}*/
multiset<pair<int,int>> lrset;
multiset<pair<int,int>> rlset;
for (int i = 0; i<n; i++){
lrset.insert({s[i],t[i]});
rlset.insert({t[i],s[i]});
}
ll tot = 0;
while (lrset.size()>1){
/*cout<<'\n';
for (auto p : lrset){
cout<<p.first<<' '<<p.second<<'\n';
}*/
auto el = lrset.begin();
int firstl = el->first;
auto smallestrpair = rlset.lower_bound({firstl+1,-1});
if (smallestrpair!=rlset.begin()&&*prev(smallestrpair,1)==make_pair(el->second,el->first)){
smallestrpair = rlset.lower_bound({el->second,el->first-1});
}
if (smallestrpair==rlset.begin()){
el = next(el,1);
firstl = el->first;
smallestrpair = rlset.lower_bound({firstl+1,-1});
if (smallestrpair!=rlset.begin()&&*prev(smallestrpair,1)==make_pair(el->second,el->first)){
smallestrpair = rlset.lower_bound({el->second,el->first-1});
}
/*if (smallestrpair==rlset.begin()){
return 1;
}*/
}
if (smallestrpair!=rlset.begin()){
smallestrpair = prev(smallestrpair,1);
}
if (*smallestrpair==make_pair(el->second,el->first)){
smallestrpair = next(smallestrpair,1);
}
//merge el with smallestrpair
int fpairl = el->first;
int fpairr = el->second;
int spairl = smallestrpair->second;
int spairr = smallestrpair->first;
//cout<<fpairl<<' '<<fpairr<<' '<<spairl<<' '<<spairr<<'\n';
lrset.erase(lrset.find({fpairl,fpairr}));
rlset.erase(rlset.find({fpairr,fpairl}));
lrset.erase(lrset.find({spairl,spairr}));
rlset.erase(rlset.find({spairr,spairl}));
lrset.insert({spairl,fpairr});
rlset.insert({fpairr,spairl});
tot+=max(0,spairr-fpairl);
}
return tot;
}
