#include <bits/stdc++.h>
#include "railroad.h"
#define ff first
#define ss second
using namespace std;

long long plan_roller_coaster(vector<int> s, vector<int> t) {
	int N =s.size();
	map<int,int> comp;
	for(int i =0; i < N; i++) comp[s[i]] =comp[t[i]] =0;
	int m =0;
	for(auto it =comp.begin(); it != comp.end(); it++) it->ss =m++;
	vector<int> dif(m,0),pos(m);
	for(auto it =comp.begin(); it != comp.end(); it++) pos[it->ss] =it->ff;
	for(int i =0; i < N; i++) {
		dif[comp[s[i]]]--;
		dif[comp[t[i]]]++;}

	vector< vector< pair<int,int> > > G(m);
	int x =1;
	long long ans =0;
	for(int i =0; i < m-1; i++) {
		x +=dif[i];
		if(x < 0) {
			ans +=1LL*(-x)*(pos[i+1]-pos[i]);
			G[i+1].push_back(make_pair(0,i));}
		if(x > 0) G[i].push_back(make_pair(0,i+1));
		G[i+1].push_back(make_pair(pos[i+1]-pos[i],i));
		G[i].push_back(make_pair(pos[i+1]-pos[i],i+1));}
	for(int i =0; i < N; i++) G[comp[s[i]]].push_back(make_pair(0,comp[t[i]]));

	priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > q;
	vector<int> vis(m,0);
	vis[0] =1;
	for(auto p:G[0]) q.push(p);
	while(!q.empty()) {
		pair<int,int> p =q.top();
		q.pop();
		if(vis[p.ss]) continue;
		for(auto r:G[p.ss]) q.push(r);
		vis[p.ss] =1;
		ans +=p.ff;}

    return ans;}