#include "wiring.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
typedef long long ll;
const ll inf=1e15;
ll min_total_length(vector<int> r, vector<int> b) {
vector<pair<ll,int> > v;
v.push_back({-inf,0});
v.push_back({-inf,1});
for(auto h:r){
v.push_back({h,0});
}
for(auto h:b){
v.push_back({h,1});
}
sort(v.begin(),v.end());
int n=v.size();
int l[2]={0,1};
vector<ll> dp(n,inf);
vector<int> f(n,0),g(n,0),from(n);
dp[1]=0;
f[1]=1;
for(int i=2;i<n;i++){
int x=l[v[i].sc];
l[v[i].sc]=i;
if(x==i-1){
f[i]=f[i-1];
int s=i-f[i];
dp[i]=min(dp[i],dp[i-1]+v[i].fs-v[f[i]-1].fs);
from[i]=from[i-1];
if(g[f[i]]>1){
g[f[i]]--;
dp[i]=min(dp[i],dp[i-1]+v[i].fs-v[f[i]].fs);
from[i]=from[i-1];
}
else{
if(f[f[i]-1]<=f[i]-1-s){
ll p=dp[i-1]+v[i].fs-v[f[i]-1-s].fs-dp[from[i-1]]+dp[f[i]-1-s-1];
from[i]=f[i]-1-s-1;
dp[i]=min(dp[i],p);
}
}
}
else{
f[i]=i;
if(x==i-2){
dp[i]=min(dp[i],min(dp[i-1],dp[i-2])+(v[i].fs-v[i-1].fs));
g[i]=1;
}
else{
ll cnt=v[i].fs-v[i-1].fs;
for(int j=i-2;j>=x;j--){
if(dp[j]+cnt<=dp[i]){
dp[i]=min(dp[i],dp[j]+cnt);
g[i]=(i-j-1);
from[i]=j;
}
cnt+=v[i].fs-v[j].fs;
}
}
}
//cout << i << " " << v[i].fs << " " << dp[i] << " " << x << "\n";
}
return dp[n-1];
}
