#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
struct Segtree {
ll l, r, val = INF;
Segtree *lf, *rg;
void build() {
if (l == r) return;
ll mid = (l+r)/2;
lf = new Segtree(), rg = new Segtree();
lf->l = l, lf->r = mid, rg->l = mid+1, rg->r = r;
lf->build(), rg->build();
}
void update(ll idx, ll z) {
if (l == r) val = z;
else {
ll mid = (l+r)/2;
if (idx <= mid) lf->update(idx, z);
else rg->update(idx, z);
val = min(lf->val, rg->val);
}
}
ll query(ll x, ll y) {
if (l > y || r < x) return INF;
if (l >= x && r <= y) return val;
return min(lf->query(x, y), rg->query(x, y));
}
};
long long min_total_length(vector<int> R, vector<int> B) {
ll N = R.size(), M = B.size();
vector <pair<ll, ll>> points(1);
vector <ll> isi[2];
for (int i = 0; i < N; i++) {
points.push_back({R[i], 0});
}
for (int i = 0; i < M; i++) {
points.push_back({B[i], 1});
}
sort(points.begin(), points.end());
ll K = N+M;
vector <ll> dp(K+5, INF), ps(K+5);
dp[0] = 0;
for (int i = 1; i <= K; i++) {
isi[points[i].second].push_back(points[i].first);
ps[i] = ps[i-1]+points[i].first;
}
vector <ll> ptr(2, -1);
auto GetSum = [&](ll l, ll r) {
return ps[r]-ps[l-1];
};
Segtree sg;
sg.l = 1, sg.r = K;
sg.build();
for (int i = 1; i <= K; i++) {
if (i == 1 || points[i].second != points[i-1].second) {
ptr[points[i].second] = i;
}
if (ptr[!points[i].second] != -1) {
dp[i] = min(dp[i], dp[i-1]+points[i].first-points[ptr[!points[i].second]].first);
}
if (ptr[points[i].second] != -1 && ptr[!points[i].second] != -1) {
ll rg = i-ptr[points[i].second]+1;
ll lf = ptr[points[i].second]-ptr[!points[i].second];
if (lf >= rg) {
ll x = ptr[points[i].second]-rg;
ll ret = GetSum(ptr[points[i].second], i)-GetSum(x, ptr[points[i].second]-1);
// cout << i << " " << ret << " CAN\n";
dp[i] = min(dp[i], ret+sg.query(ptr[!points[i].second], x)-ps[x-1]+(x-1)*points[ptr[points[i].second]].first);
}
}
// cout << dp[i] << " " << i << " HERE\n";
auto it = upper_bound(isi[!points[i].second].begin(), isi[!points[i].second].end(), points[i].first);
if (it != isi[!points[i].second].end()) {
ll ret = dp[i-1]-(*it)*(i-1)+ps[i-1];
// cout << i << " " << ret << " UPDATE VAL\n";
sg.update(i, ret);
}
}
return dp[K];
}
/*
ps[]
*/
