#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair <int,int> ii;
vector <int> DSU;
int find_parent(int a)
{
if(DSU[a]==a)
{
return a;
}
return DSU[a]=find_parent(DSU[a]);
}
bool make_union(int a, int b)
{
a=find_parent(a);
b=find_parent(b);
if(a==b)
{
return 0;
}
DSU[b]=a;
return 1;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
int n = (int) s.size();
vector <ii> nw_s;
vector <ii> nw_t;
for(int i=0;i<n;i++)
{
nw_s.pb(ii(s[i],i));
nw_t.pb(ii(t[i],i));
}
vector <ii> nw;
sort(nw_s.begin(),nw_s.end());
sort(nw_t.begin(),nw_t.end());
for(int i=0;i<n-1;i++)
{
nw.pb(ii(nw_t[i].second,nw_s[i+1].second));
}
nw.pb(ii(nw_t[n-1].second,nw_s[0].second));
DSU=vector <int> (n);
for(int i=0;i<n;i++)
{
DSU[i]=i;
}
ll ans=0;
priority_queue <ii> pq;
for(int i=0;i<n;i++)
{
make_union(nw[i].first,nw[i].second);
if(i!=n-1)
{
ans+=max(t[nw[i].first]-s[nw[i].second],0);
pq.push(ii(i,max(t[nw[i+1].first]-s[nw[i].second],0)+max(t[nw[i].first]-s[nw[i+1].second],0)-max(t[nw[i].first]-s[nw[i].second],0)-max(t[nw[i+1].first]-s[nw[i+1].second],0)));
}
}
for(int i=0;i<n;i++)
{
//printf("%d %d\n",t[nw[i].first],s[nw[i].second]);
}
while(pq.size())
{
int ptr=pq.top().first;
int num=pq.top().second;
pq.pop();
if(make_union(nw[ptr].first,nw[ptr+1].first))
{
ans+=max(0,num);
}
}
return ans;
}
