#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector <int> r,vector <int> b){
vector <pair <int,int> > vec;
for (int i=0; i<r.size(); i++) vec.push_back({r[i],0});
for (int i=0; i<b.size(); i++) vec.push_back({b[i],1});
sort(vec.begin(),vec.end());
int n=vec.size();
vec.insert(vec.begin(),{0,0});
long long dp[n+1];
vector <pair <int,int> > rgs;
for (int i=1; i<=n; i++){
if (i==1) rgs.push_back({1,1});
else if (vec[i].second==vec[i-1].second) rgs.back().second++;
else rgs.push_back({i,i});
}
dp[0]=0;
for (int i=1; i<=rgs[0].second; i++) dp[i]=dp[i-1]+vec[rgs[1].first].first-vec[i].first;
for (int i=1; i<rgs.size(); i++){
multiset <long long> ms;
long long sum=0,cnt=0;
map <int,long long> mp;
for (int j=rgs[i-1].second; j>=rgs[i-1].first; j--){
sum+=vec[rgs[i-1].second].first-vec[j].first;
cnt++;
long long val=dp[j-1]+sum+cnt*(vec[rgs[i].first].first-vec[rgs[i-1].second].first);
ms.insert(val);
mp[cnt]=val;
}
sum=0; cnt=0;
long long rem=1e18;
for (int j=rgs[i].first; j<=rgs[i].second; j++){
sum+=vec[j].first-vec[rgs[i].first].first;
cnt++;
long long mx=rem+cnt*(vec[rgs[i].first].first-vec[rgs[i-1].second].first);
if (!ms.empty()) mx=min(mx,*ms.begin());
dp[j]=sum+mx;
if (mp.find(cnt)!=mp.end()){
long long val=mp[cnt];
ms.erase(ms.find(val));
val-=cnt*(vec[rgs[i].first].first-vec[rgs[i-1].second].first);
rem=min(rem,val);
}
}
for (int j=rgs[i].second-1; j>=rgs[i-1].first; j--) dp[j]=min(dp[j],dp[j+1]);
}
return dp[n];
}
