#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1234567890;
int n;
pair<int,int> arr[1000005];
set<int> sa, sb;
int getnearest(int x){
int res = 2e9;
if(arr[x].second == 1){
auto p = sa.lower_bound(arr[x].first);
if(p != sa.end()){
res = min(res,*p-arr[x].first);
}
if(p != sa.begin()){
p--;
res = min(res,arr[x].first-*p);
}
}
else{
auto p = sb.lower_bound(arr[x].first);
if(p != sb.end()){
res = min(res,*p-arr[x].first);
}
if(p != sb.begin()){
p--;
res = min(res,arr[x].first-*p);
}
}
return res;
}
ll prefa[1000005], prefb[1000005];
ll dp[1000005];
int mat[1000005], prv[2000005];
long long min_total_length(vector<int> aa, vector<int> bb) {
int p = aa.size();
int q = bb.size();
for(int i = 1;i<=p;++i){
arr[i].first = aa[i-1]; arr[i].second = -1;
sa.insert(aa[i-1]);
}
for(int i = 1;i<=q;++i){
arr[i+p].first = bb[i-1]; arr[i+p].second = 1;
sb.insert(bb[i-1]);
}
n = p+q;
sort(arr+1, arr+n+1);
memset(mat, -1, sizeof(mat));
memset(prv, -1, sizeof(prv));
prv[n] = 0;
int cur = n;
for(int i = 1;i<=n;++i){
prefa[i] = prefa[i-1]; prefb[i] = prefb[i-1];
if(arr[i].second == -1){
prefa[i] += arr[i].first;
cur++;
}
else{
prefb[i] += arr[i].first;
cur--;
}
if(prv[cur] >= 0) mat[i] = prv[cur];
prv[cur] = i;
}
for(int i = 1;i<=n;++i){
dp[i] = dp[i-1]+getnearest(i);
if(~mat[i]){
dp[i] = min(dp[i],dp[mat[i]] + abs(prefa[i]-prefa[mat[i]]-prefb[i]+prefb[mat[i]]));
}
}
return dp[n];
}
