/**
* author: m371
* created: 03.11.2021 23:07:51
**/
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
int n = r.size() + b.size();
vector<pair<int, int>> a;
for (int i = 0; i < (int) r.size(); i++) {
a.emplace_back(r[i], 0);
}
for (int i = 0; i < (int) b.size(); i++) {
a.emplace_back(b[i], 1);
}
sort(a.begin(), a.end());
vector<pair<int, int>> segs;
for (int i = 0; i < n; i++) {
int ptr = i;
while (ptr + 1 < n && a[i].second == a[ptr + 1].second) {
ptr += 1;
}
segs.emplace_back(i, ptr);
i = ptr;
}
int sz = segs.size();
vector<long long> dp(n);
vector<vector<long long>> pref(sz);
vector<vector<long long>> suff(sz);
for (int i = 0; i < sz; i++) {
int l = segs[i].first;
int r = segs[i].second;
int len = r - l + 1;
vector<long long> aux(len);
for (int j = len - 1; j >= 0; j--) {
if (j + 1 < len) {
aux[j] = aux[j + 1];
}
aux[j] += a[r].first - a[l + j].first;
}
long long sum = 0;
const long long inf = (long long) 1e17;
for (int j = 0; j < len; j++) {
sum += (a[l + j].first - a[l].first);
if (i == 0) {
dp[j + l] = inf;
} else {
int prv_sz = suff[i - 1].size();
dp[j + l] = inf;
dp[j + l] = min(dp[j + l], suff[i - 1][prv_sz - min(prv_sz, j + 1)] + sum + (j + 1) * 1LL * (a[l].first - a[l - 1].first));
if (prv_sz > j + 1) {
dp[j + l] = min(dp[j + l], pref[i - 1][prv_sz - j - 2] + sum);
}
}
}
if (i + 1 == sz) {
continue;
}
pref[i].resize(len);
suff[i].resize(len);
for (int j = 0; j < len; j++) {
pref[i][j] = aux[j] + (l + j > 0 ? dp[l + j - 1] : 0LL) + (len - j) * 1LL * (a[r + 1].first - a[r].first);
if (j > 0) {
pref[i][j] = min(pref[i][j], pref[i][j - 1]);
}
}
for (int j = len - 1; j >= 0; j--) {
suff[i][j] = aux[j] + (l + j > 0 ? dp[l + j - 1] : 0LL);
if (j + 1 < len) {
suff[i][j] = min(suff[i][j], suff[i][j + 1]);
}
}
}
return dp[n - 1];
}
