#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
long long min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
vector<pair<int, int>> all;
for (int i = 0; i < n; i++) {
all.emplace_back(r[i], 0);
}
for (int i = 0; i < m; i++) {
all.emplace_back(b[i], 1);
}
sort(all.begin(), all.end());
vector<vector<int>> blocks;
vector<int> cur;
int color = all[0].second;
for (int i = 0; i < n + m; i++) {
if (color == all[i].second) {
cur.push_back(all[i].first);
} else {
blocks.push_back(cur);
cur.clear();
color = all[i].second;
cur.push_back(all[i].first);
}
}
blocks.push_back(cur);
vector<vector<long long>> dp(blocks.size()), suff(blocks.size()), pref(blocks.size());
for (int i = 0; i < blocks.size(); i++) {
dp[i].resize(blocks[i].size() + 1);
fill(dp[i].begin(), dp[i].end(), inf);
pref[i].resize(blocks[i].size() + 1);
fill(pref[i].begin(), pref[i].end(), inf);
suff[i].resize(blocks[i].size() + 1);
fill(suff[i].begin(), suff[i].end(), inf);
}
dp[0][0] = 0;
{
long long x0 = blocks[0].back(), y0 = blocks[1][0];
long long sum = accumulate(blocks[0].begin(), blocks[0].end(), 0LL);
for (int i = 0; i <= blocks[0].size(); i++) {
long long here = dp[0][i] + static_cast<long long>(y0) * static_cast<long long>(blocks[0].size() - i) - sum;
pref[0][i] = here;
if (i > 0) {
pref[0][i] = min(pref[0][i - 1], here);
}
if (i != blocks[0].size()) {
sum -= blocks[0][i];
}
}
for (int i = blocks[0].size(); i >= 0; i--) {
long long here = dp[0][i] + static_cast<long long>(blocks[0].size() - i) * static_cast<long long>(x0) - sum;
suff[0][i] = here;
if (i < blocks[0].size()) {
suff[0][i] = min(suff[0][i + 1], here);
}
if (i != 0) {
sum += blocks[0][i - 1];
}
}
}
for (int i = 1; i < blocks.size(); i++) {
{
long long sum = 0, x0 = blocks[i - 1].back(), y0 = blocks[i][0];
dp[i][0] = dp[i - 1][blocks[i - 1].size()];
for (int j = 1; j <= blocks[i].size(); j++) {
sum += blocks[i][j - 1];
long long rn = sum - (static_cast<long long>(j) * static_cast<long long>(y0));
// blocks[i - 1].size() - k >= j
// blocks[i - 1].size() - j >= k
if (int(blocks[i - 1].size()) - j >= 0) {
dp[i][j] = min(dp[i][j], pref[i - 1][int(blocks[i - 1].size()) - j] + rn);
}
rn = sum - (static_cast<long long>(j) * static_cast<long long>(x0));
dp[i][j] = min(dp[i][j], rn + suff[i - 1][max(int(int(int(blocks[i - 1].size()) - j)), 0)]);
}
}
{
if (i + 1 == blocks.size()) {
break;
}
long long x0 = blocks[i].back(), y0 = blocks[i + 1][0];
long long sum = accumulate(blocks[i].begin(), blocks[i].end(), 0LL);
for (int j = 0; j <= blocks[i].size(); j++) {
long long here = dp[i][j] + static_cast<long long>(y0) * static_cast<long long>(blocks[i].size() - j) - sum;
pref[i][j] = here;
if (j > 0) {
pref[i][j] = min(pref[i][j - 1], here);
}
if (j != blocks[i].size()) {
sum -= blocks[i][j];
}
}
for (int j = blocks[i].size(); j >= 0; j--) {
long long here = dp[i][j] + static_cast<long long>(blocks[i].size() - j) * static_cast<long long>(x0) - sum;
suff[i][j] = here;
if (j != blocks[i].size()) {
suff[i][j] = min(suff[i][j + 1], here);
}
if (j != 0) {
sum += blocks[i][j - 1];
}
}
}
}
return dp[blocks.size() - 1][blocks.back().size()];
}
