#include "wiring.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
const int inf = 1e18;
vi p;
vi a;
int get(int l,int r,int l2,int r2) {
int n1 = r-l+1,n2 = r2-l2+1;
int s1 = p[r]-p[l-1],s2 = p[r2]-p[l2-1];
if (n2 >= n1) {
return (s2-s1)-(n2-n1)*a[r];
}
else {
return (n1-n2)*a[l2]+(s2-s1);
}
}
int min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
int n = r.size()+b.size();
vector<pii> pts;
for (auto it : r) pts.push_back({it,0});
for (auto it : b) pts.push_back({it,1});
sort(all(pts));
p.assign(n+1,0);
a.assign(n+1,0);
for (int i=1;i<=n;i++) a[i] = pts[i-1].ff;
for (int i=1;i<=n;i++) p[i] = p[i-1]+a[i];
pii lst{-1,-1};
vi dp(n+1,0);
for (int i = 1;i<=n;) {
int j = i;
while (j<n && pts[j].ss == pts[i-1].ss) j++;
//i..j
for (int k = i;k<=j;k++) dp[k] = inf;
if (lst != pii{-1,-1}) {
int opt = lst.ss;
for (int k = i;k<=j;k++) {
int opty = opt;
int best = 2e18;
int vista = inf;
for (int tr = opty; tr >= lst.ff; tr--) {
vista = min(vista,dp[tr]);
vista = min(vista,dp[tr-1]);
int cost = vista+get(tr,i-1,i,k);
if (cost <= best) {
best = cost;
opt = tr;
}
}
dp[k] = best;
}
}
lst = {i,j};
i = j+1;
}
return dp[n];
}
