#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;
ll min_total_length(vector<int> r, vector<int> b) {
vector<pii> v0;
for (ll x: r) {
v0.push_back({x,0});
}
for (ll x: b) {
v0.push_back({x,1});
}
sort(v0.begin(),v0.end());
ll N = v0.size();
vector<ll> dist0(N,INF),dist1(N,INF); //min distance from 0 or 1
ll x0max = -INF; ll x1max=-INF;
for (ll i=0;i<N;i++) {
pii p0 = v0[i];
if (p0.second==0) {
x0max = p0.first;
} else {
x1max = p0.first;
}
dist0[i]=min(dist0[i],p0.first-x0max);
dist1[i]=min(dist1[i],p0.first-x1max);
}
ll x0min = INF; ll x1min=INF;
for (ll i=(N-1);i>=0;i--) {
pii p0 = v0[i];
if (p0.second==0) {
x0min = p0.first;
} else {
x1min = p0.first;
}
dist0[i]=min(dist0[i],-p0.first+x0min);
dist1[i]=min(dist1[i],-p0.first+x1min);
}
vector<pii> dpt[N]; //dp transition: (final x, value)
//initial/final x: # of things already processed
for (ll i=0;i<N;i++) {
pii p0 = v0[i];
if (p0.second==0) {
dpt[i].push_back({i+1,dist1[i]});
} else {
dpt[i].push_back({i+1,dist0[i]});
}
}
for (ll x=0;x<(N-1);x++) {
ll fval = 0;
ll yc = 0;
while ((x-yc)>=0 && (x+1+yc)<N && v0[x-yc].second==0 && v0[x+yc+1].second==1) {
fval += v0[x+yc+1].first - v0[x-yc].first;
dpt[x-yc].push_back({x+yc+2,fval});
yc++;
}
fval = 0; yc = 0;
while ((x-yc)>=0 && (x+1+yc)<N && v0[x-yc].second==1 && v0[x+yc+1].second==0) {
fval += v0[x+yc+1].first - v0[x-yc].first;
dpt[x-yc].push_back({x+yc+2,fval});
yc++;
}
}
vector<ll> dp(N+1,INF);
dp[0]=0;
for (ll x=0;x<N;x++) {
for (pii p0: dpt[x]) {
dp[p0.first]=min(dp[p0.first],dp[x]+p0.second);
}
}
return dp[N];
}
