#include <bits/stdc++.h>
using namespace std;
#include "railroad.h"
struct Vertex {
vector<pair<long long, int>> connections;
};
map<int, Vertex> vertices;
map<int, bool> visited;
long long MST(int s)
{
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push(make_pair(0, s));
long long distance = 0;
while (!pq.empty())
{
pair<long long, int> top = pq.top(); pq.pop();
if (visited[top.second]) continue;
else visited[top.second] = true;
distance += top.first;
for (pair<long long, int> connection : vertices[top.second].connections) {
pq.push(make_pair(connection.first, connection.second));
}
}
return distance;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
int n = (int) s.size();
map<int, int> interest;
interest[1]--;
for (int i = 0; i < n; i++)
{
interest[s[i]]++;
interest[t[i]]--;
vertices[s[i]].connections.push_back(make_pair(0, t[i]));
vertices[t[i]].connections.push_back(make_pair(0, s[i]));
}
auto itr = interest.begin();
long long value = (*itr).second;
long long balance = max((long long) 0, value);
auto prev = itr++;
for (; itr != interest.end(); itr++)
{
value += (*itr).second;
balance += max((long long) 0, value);
long long _weight = (*itr).first - (*prev).first;
if (value < 0) _weight = 0;
vertices[(*prev).first].connections.push_back(make_pair(_weight, (*itr).first));
vertices[(*itr).first].connections.push_back(make_pair(_weight, (*prev).first));
prev = itr;
}
for (pair<int, int> p : interest)
{
value += p.second;
balance += max((long long) 0, value);
}
balance += MST(s[0]);
return balance;
}
