#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
const int MAXN=2e5+10;
const ll inf=1e16;
typedef pair<ll,ll> pii;
typedef tuple<int,int,int> trio;
int best[MAXN],n,m,tam[MAXN];
vector<pii> v,g;
vector<vector<ll>> pref,pf,dp;
int dist(int a,int b){
return abs(v[a].F-v[b].F);
}
void dnc(int l,int r,int optl,int optr,int i){
if(l>r) return;
int mei=(l+r)>>1;
int opt; dp[i][mei]=inf;
fall(j,optl,min(tam[i]-mei,tam[i+1])){
ll custo=dp[i+1][j]+pref[i+1][j]-(pref[i].back()-pref[i][tam[i]-j])+pf[i][tam[i]-j]-pf[i][mei];
if(custo<dp[i][mei]){
dp[i][mei]=custo;
opt=j;
}
}
dnc(l,mei-1,opt,optr,i); dnc(mei+1,r,optl,opt,i);
}
long long min_total_length(std::vector<int> r, std::vector<int> b){
n=sz(r),m=sz(b);
v.resize(n+m);
fall(i,0,n-1) v[i]={r[i],0};
fall(i,0,m-1) v[i+n]={b[i],1};
sort(all(v));
fall(i,0,m+n-1){
int r=i;
while(r!=n+m-1 && v[r+1].S==v[r].S) r++;
g.pb({i,r});
i=r;
}
pref.resize(sz(g)); dp.resize(sz(g)); pf.resize(sz(g));
fall(i,0,sz(g)-1){
tam[i]=g[i].S-g[i].F+1;
pref[i].resize(tam[i]+1); dp[i].resize(tam[i]+1); pf[i].resize(tam[i]+1);
fall(r,g[i].F,g[i].S){
pref[i][r-g[i].F+1]=pref[i][r-g[i].F]+v[r].F;
if(i+1==sz(g)){
best[r]=dist(r,g[i-1].S);
}
else if(!i) best[r]=dist(r,g[i+1].F);
else best[r]=min(dist(r,g[i+1].F),dist(r,g[i-1].S));
pf[i][r-g[i].F+1]=pf[i][r-g[i].F]+best[r];
}
}
fall(i,g.back().F-1,g.back().S){
int x=i-g.back().F+1;
dp[sz(g)-1][x]=pf[sz(g)-1].back()-pf[sz(g)-1][x];
}
rfall(i,sz(g)-2,0){
dnc(0,g[i].S-g[i].F+1,0,g[i+1].S-g[i+1].F+1,i);
}
return dp[0][0];
}
