#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
using ll=long long;
const ll TAILLE_MAX=100*1000+5,INFINI=(ll)1000*1000*1000*1000*1000;
ll nbRouge,nbBleu;
vector<ll> posBleu,posRouge;
unordered_map<ll,ll> memo;
set<pair<ll,ll>> listeBleu,listeRouge;
ll dyna(ll idRouge,ll idBleu) {
if (idRouge==nbRouge and idBleu==nbBleu) {
return 0;
}
if (idRouge==nbRouge or idBleu==nbBleu) {
return INFINI;
}
ll caseTab=idRouge*TAILLE_MAX+idBleu;
ll ans=memo[caseTab];
if (ans==0) {
return INFINI;
}
if (ans>0) {
return ans;
}
ans=abs(posRouge[idRouge]-posBleu[idBleu])+min(min(dyna(idRouge,idBleu+1),dyna(idRouge+1,idBleu)),dyna(idRouge+1,idBleu+1));
memo[caseTab]=ans;
//cout<<idRouge<<" "<<idBleu<<" : "<<ans<<endl;
return ans;
}
ll min_total_length(vector<int> r,vector<int> b) {
nbRouge=r.size();
nbBleu=b.size();
for (int i=0;i<nbRouge;i++) {
posRouge.push_back(r[i]);
listeRouge.insert({r[i],i});
}
for (int i=0;i<nbBleu;i++) {
posBleu.push_back(b[i]);
listeBleu.insert({b[i],i});
}
listeRouge.insert({-INFINI,-1});
listeRouge.insert({INFINI,-1});
listeBleu.insert({-INFINI,-1});
listeBleu.insert({INFINI,-1});
set<pair<ll,ll>>::iterator it;
for (int i=0;i<nbRouge;i++) {
it=listeBleu.lower_bound({posRouge[i],0});
if ((*it).second!=-1) {
memo[i*TAILLE_MAX+(*it).second]=-1;
}
it--;
if ((*it).second!=-1) {
memo[i*TAILLE_MAX+(*it).second]=-1;
}
}
for (int i=0;i<nbBleu;i++) {
it=listeRouge.lower_bound({posBleu[i],0});
if ((*it).second!=-1) {
memo[(*it).second*TAILLE_MAX+i]=-1;
}
it--;
if ((*it).second!=-1) {
memo[(*it).second*TAILLE_MAX+i]=-1;
}
}
return dyna(0,0);
}
