#include "wiring.h"
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
int ps[200001];
int pre[200001][2];
int dp[200001];
vector<pair<int, int>> vp;
int sum(int l, int r){
return ps[r + 1] - ps[l];
}
int n, m;
int cost(int l, int r){
assert(l < r && l >= 0 && r < n + m);
int lr = pre[r][!vp[r].se];
int lsz = lr - l + 1;
int rsz = r - lr;
int _m = min(lsz, rsz);
int ret = sum(lr + 1, lr + _m) - sum(lr - _m + 1, lr);
if(lsz >= rsz){
return ret + (lsz - rsz) * vp[lr + 1].fi - sum(l, lr - _m);
}else{
return ret + sum(lr + _m + 1, r) - (rsz - lsz) * vp[lr].fi;
}
}
long long min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
n = r.size(); m = b.size();
for(int i = 0; i < n; i++) vp.push_back({r[i], 0});
for(int i = 0; i < m; i++) vp.push_back({b[i], 1});
sort(vp.begin(), vp.end());
for(int i = 0; i < n + m; i++){
ps[i + 1] = ps[i] + vp[i].fi;
}
for(int i = 0; i < n + m; i++){
pre[i][vp[i].se] = i;
pre[i][!vp[i].se] = (i == 0 ? -1 : pre[i - 1][!vp[i].se]);
}
dp[0] = 0;
fill(dp + 1, dp + n + m + 1, 1LL << 60);
int opt = -1;
for(int i = 0; i < n + m; i++){
if(pre[i][!vp[i].se] == -1) continue;
if(vp[i].se != vp[i - 1].se) opt = dp[pre[i][!vp[i].se] + 1] == 1LL << 60 ? 0 : pre[i][!vp[i].se];
while(opt > 0 && vp[opt - 1].se != vp[i].se && min(dp[opt], dp[opt - 1]) + cost(opt - 1, i) <= dp[opt] + cost(opt, i)) opt--;
dp[i + 1] = min(dp[opt + 1], dp[opt]) + cost(opt, i);
}
return dp[n + m];
}
