#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
vector<long long> transformation(vector<int> idxa,vector<int> idxb,vector<long long> DPa) {
int A = idxa.size()-1;
int B = idxb.size()-1;
vector DPres(B+1,INF);
DPres[0]=DPa.back();
if(A==0)return DPres;
vector<long long> centerhelp(B+1);
{
// Center Outwards Transformation
int lastA = idxa.back();
long long sum = 0;
long long curropt = INF;
int otherIDX = A+1;
for(int i=1;i<=B;i++) {
otherIDX--;
if(i<=A)sum+=idxb[i]-idxa[otherIDX];
centerhelp[i]=sum;
curropt+=idxb[i]-lastA;
if(i<=A)curropt = min(curropt,min(DPa[otherIDX],DPa[otherIDX-1])+sum);
DPres[i]=min(DPres[i],curropt);
}
}
{
// Inwards transformation
long long sum = 0;
long long curropt = INF;
int cntCenterTransformation = min(A,B);
idxb.erase(idxb.begin()+cntCenterTransformation+1,idxb.end());
B = idxb.size()-1;
int FirstB = idxb[1];
long long base = centerhelp[B];
long long lastOpt = INF;
for(int i=A-B;i;i--) {
base+=FirstB-idxa[i];
lastOpt = min(lastOpt,min(DPa[i],DPa[i-1])+base);
DPres[B]=min(DPres[B],min(DPa[i],DPa[i-1])+base);
}
for(int i=B;i;i--){
int otherIDX = A+1-i;
if(i==B) {
curropt=min(curropt,lastOpt);
} else {
curropt+=FirstB-idxb[i+1];
}
curropt=min(curropt,min(DPa[otherIDX],DPa[otherIDX-1])+centerhelp[i]);
DPres[i]=min(DPres[i],curropt);
}
}
return DPres;
}
long long min_total_length(vector<int> r, vector<int> b) {
vector<pair<int,int>> arr;
for(int&i:b)arr.emplace_back(i,0);
for(int&i:r)arr.emplace_back(i,1);
sort(arr.begin(), arr.end());
int n = arr.size();
arr.insert(arr.begin(),{-1,0});
arr.emplace_back(1e9+1,2);
vector DPlast(1,0ll);
vector lastidx(1,-1);
vector curridx(1,-1);
for(int i=1;i<=n;i++) {
auto [idx,mycolour] = arr[i];
curridx.emplace_back(idx);
if(arr[i+1].second==mycolour)continue;
DPlast = transformation(lastidx,curridx,DPlast);
swap(curridx,lastidx);
curridx.clear();
curridx.emplace_back(-1);
}
return DPlast.back();
}
