#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define ll long long
#define pi pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define int ll
const int inf = 1e18;
int cost(vector<pi>&a, vector<int>&pr, int nw, int i, int j) {
int fcnt = nw - j;
int scnt = i - nw + 1;
int fsum = pr[nw] - pr[j];
int ssum = pr[i+1] - pr[nw];
if (fcnt < scnt) {
fsum += a[nw-1].f * (scnt-fcnt);
}
if (scnt < fcnt) {
ssum += a[nw].f * (fcnt-scnt);
}
return ssum - fsum;
}
int min_total_length(vector<int32_t> r, vector<int32_t> b) {
int n=r.size(),m=b.size();
vector<pi> a;
forn(i,n) a.pb({r[i],0});
forn(i,m) a.pb({b[i],1});
sort(all(a));
vector<int> dp(n+m+1,inf);
dp[0]=0;
vector<int> opt(n+m+1,-1);
int i=0;
while (a[i].s==a[0].s) ++i;
int old=0, nw=i;
vector<int> pr(n+m+1);
forn(i,n+m) pr[i+1]=pr[i]+a[i].f;
dp[i+1] = cost(a,pr,i,i,0);
opt[i+1] = 0;
++i;
for (;i<n+m;++i) {
if (a[i].s != a[i-1].s) {
old=nw;
nw=i;
int j=nw-1;
for (; j>old; --j) {
int x = dp[j]+cost(a,pr,nw,i,j);
int y = dp[j-1]+cost(a,pr,nw,i,j-1);
if (y>x) break;
}
opt[i+1] = j;
dp[i+1] = min(dp[j],dp[j+1])+cost(a,pr,nw,i,j);
} else {
int j=opt[i];
for (; j>old; --j) {
int x = dp[j]+cost(a,pr,nw,i,j);
int y = dp[j-1]+cost(a,pr,nw,i,j-1);
if (y>x) break;
}
opt[i+1] = j;
dp[i+1] = min(dp[j],dp[j+1])+cost(a,pr,nw,i,j);
}
}
return dp[n+m];
}
#undef int
