#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()
const ll inf = 1e18;
#define int ll
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) {
//cout<<"? "<<ssum<<": "<<fcnt<<' '<<scnt<<' '<<a[nw].f<<' '<<fcnt-scnt<<'\n';
ssum += a[nw].f * (fcnt-scnt);
}
//cout<<"! cost "<<j<<' '<<nw<<' '<<i<<": "<<fcnt<<' '<<scnt<<' '<<fsum<<' '<<ssum<<" "<<ssum-fsum<<'\n';
return ssum - fsum;
}
#undef int
ll min_total_length(vector<int> r, vector<int> b) {
#define int ll
int n=r.size(),m=b.size();
const int inf = 1e18;
vector<pi> a;
forn(i,n) a.pb({r[i],0});
forn(i,m) a.pb({b[i],1});
sort(all(a));
//if (a.back().f>n+m) return 0;
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, nw=0;
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);
++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] = dp[j]+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);
//cout<<"! "<<i<<' '<<j<<' '<<x<<' '<<y<<'\n';
if (y>x) break;
}
opt[i+1] = j;
dp[i+1] = dp[j]+cost(a,pr,nw,i,j);
}
}
//forn(i,n+m+1) cout<<dp[i]<<' '; cout<<'\n';
return dp[n+m];
#undef int
}
