#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dsu
{
vector<int> par;
int cnt;
dsu (int sz)
{
cnt = sz;
par = vector<int>(sz);
for (int i = 0; i < sz; i++)
par[i]=i;
}
int mnz(int x)
{
return par[x] = (x == par[x] ? x : mnz(par[x]));
}
void zd(int x, int y)
{
x=mnz(x);
y=mnz(y);
if (x==y)return;
cnt--;
par[y]=x;
}
};
const ll inf = 1e9;
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
s.push_back(inf);
t.push_back(1);
int n = (int)s.size();
vector<array<ll, 3>> a;
for (int i = 0; i < n; i++)
{
a.push_back({s[i], 1, i});
a.push_back({t[i], -1, i});
}
// a.push_back({1, -1, n});
// a.push_back({0, -1, n});
sort(a.begin(), a.end(), [](array<ll, 3>&p, array<ll, 3>&d){return p[0]<d[0];});
ll rez = 0, st = 0;
dsu ds(n);
vector<array<ll, 3>> edges;
for (int i = 0; i < 2*n-1; i++)
{
st+=a[i][1];
rez+=max(0ll, st)*(a[i+1][0]-a[i][0]);
edges.push_back({a[i+1][0]-a[i][0], a[i+1][2], a[i][2]});
if (st || a[i+1][0]==a[i][0])
ds.zd(a[i+1][2], a[i][2]);
}
sort((edges).begin(), edges.end(), [](array<ll, 3>&p, array<ll, 3>&d){return p[0]<d[0];});
for (int i = 0; i < 2*n-1; i++)
{
if (ds.mnz(edges[i][2]) != ds.mnz(edges[i][1]))
{
ds.zd(edges[i][2], edges[i][1]);
rez += edges[i][0];
}
}
return rez;
}
