#include <bits/stdc++.h>
#include "railroad.h"
using namespace std;
long long plan_roller_coaster(vector<int> s, vector<int> t)
{
long long N = (long long)s.size();
vector<pair<long long, long long>> deb, fin;
for (long long i = 0; i < N; i++)
deb.push_back({t[i], i}), fin.push_back({s[i], i});
deb.push_back({0, N});
fin.push_back({1000000001, N});
sort(deb.begin(), deb.end());
sort(fin.begin(), fin.end());
long long best = 0;
vector<long long> cycle(N + 1, -1), inv(N + 1);
for (long long i = 0; i <= N; i++)
inv[deb[i].second] = i;
for (long long i = 0; i <= N; i++)
best += max(0LL, deb[i].first - fin[i].first);
vector<vector<long long>> cycles;
for (long long i = 0; i <= N; i++)
{
if (cycle[i] != -1)
continue;
cycles.push_back({});
long long x = inv[i];
while (cycle[deb[x].second] == -1)
{
cycle[deb[x].second] = cycles.size() - 1;
cycles.back().push_back(deb[x].second);
x = inv[fin[x].second];
}
}
long long nb = cycles.size();
priority_queue<vector<long long>> PQ;
for (long long i = 0; i < N; i++)
PQ.push({-(max(0LL, deb[i + 1].first - fin[i].first) + max(0LL, deb[i].first - fin[i + 1].first) - max(0LL, deb[i + 1].first - fin[i + 1].first) - max(0LL, deb[i].first - fin[i].first)), i, i + 1, 0});
vector<long long> l(N + 2, N + 1), r(N + 2, N + 1), last(N + 2);
for (long long i = 0; i <= N; i++)
l[i] = i - 1, r[i] = i + 1;
l[0] = N + 1, r[N] = N + 1;
long long buff = 0;
while (!PQ.empty())
{
long long cost = -PQ.top()[0], x = PQ.top()[1], y = PQ.top()[2], L = PQ.top()[3];
PQ.pop();
if (cycle[deb[x].second] == cycle[deb[y].second])
continue;
if (last[x] > L || last[y] > L)
continue;
best += cost;
long long c1 = cycle[deb[x].second], c2 = cycle[deb[y].second];
if (cycles[c2].size() > cycles[c1].size())
swap(c1, c2);
for (long long i = 0; i < cycles[c2].size(); i++)
{
cycles[c1].push_back(cycles[c2][i]);
cycle[cycles[c2][i]] = c1;
}
last[x] = last[y] = ++buff;
deb[y].first = deb[x].first;
r[l[x]] = r[x];
l[r[x]] = l[x];
long long a = l[x], b = r[x];
if (a == N + 1 || b == N + 1)
continue;
PQ.push({-(max(0LL, deb[b].first - fin[a].first) + max(0LL, deb[a].first - fin[b].first) - max(0LL, deb[b].first - fin[b].first) - max(0LL, deb[a].first - fin[a].first)), a, b, buff});
}
return best;
}
