#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);
}
}
vi dp;
void dnq(int l,int r,int optl,int optr,int ls,int mn) {
if (l > r) return;
int opt = optl;
int best = inf;
int m = (l+r) >> 1;
for (int i = optr;i>=optl;i--) {
int cost = min(mn,dp[i-1])+get(i,ls,ls+1,m);
if (cost <= best) {
best = cost;
opt = i;
}
}
dp[m] = best;
dnq(l,m-1,opt,optr,ls,mn),dnq(m+1,r,optl,opt,ls,mn);
}
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);
dp.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};
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}) {
dnq(i,j,lst.ff,lst.ss,i-1,dp[lst.ss]);
}
lst = {i,j};
i = j+1;
}
return dp[n];
}
