#include "wiring.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf64 = 1ll << 50;
void chmin(i64 &a, i64 b) {
if (a > b) a = b;
}
i64 solve(std::vector<i64> r, std::vector<i64> b) {
std::vector<std::pair<i64, bool>> points;
for (const auto e : r) {
points.push_back({e, true});
}
for (const auto e : b) {
points.push_back({e, false});
}
std::sort(points.begin(), points.end());
std::vector<std::vector<i64>> seqs;
bool lastType = true;
for (int i = 0; i < (int)points.size(); ++i) {
if (i == 0 or lastType != points[i].second) {
seqs.push_back({});
lastType = points[i].second;
}
seqs.back().push_back(points[i].first);
}
const int S = (int)seqs.size();
std::vector<i64> dp = {0};
for (int x = 0; x < S; ++x) {
const auto &seq = seqs[x];
const int T = (int)seq.size();
std::vector<i64> seqSum(T + 1);
for (int i = 0; i < T; ++i) {
seqSum[i + 1] = seq[i];
seqSum[i + 1] += seqSum[i];
}
auto rangeSum = [&](int l, int r) {
return seqSum[r] - seqSum[l];
};
std::vector<i64> updateMin(T + 1, inf64);
for (int i = 0; i < std::min((int)dp.size(), T + 1); ++i) {
const i64 u = dp[i] + rangeSum(0, i) - rangeSum(i, T);
chmin(updateMin[T - i], u);
}
for (int i = 0; i < T; ++i) {
chmin(updateMin[i + 1], updateMin[i] - seq[T - 1]);
}
if (x != S - 1) {
while ((int)updateMin.size() <= (int)seqs[x + 1].size()) {
updateMin.push_back(updateMin.back() - seq[T - 1]);
}
for (int i = (int)updateMin.size() - 2; i >= 0; --i) {
chmin(updateMin[i], updateMin[i + 1] + seqs[x + 1][0]);
}
}
dp = std::move(updateMin);
}
return dp[0];
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
std::vector<i64> r64, b64;
for (const auto e : r) {
r64.push_back(e);
}
for (const auto e : b) {
b64.push_back(e);
}
return solve(r64, b64);
}
