#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
#define inf 1000'000'000'000'000'000LL
template<typename T>
using vec = vector<T>;
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
template<typename it>
struct SparseTable {
using T = typename remove_reference<decltype(*declval<it>())>::type;
vector<vector<T>> t;
function<T(T, T)> f;
vector<int> log;
SparseTable() = default;
SparseTable(it first, it last, function<T(T, T)> op) : t(1), f(op) {
int n = distance(first, last);
t.assign(32 - __builtin_clz(n), vector<T>(n));
t[0].assign(first, last);
// calc log
log.resize(n + 1);
for (int i = 2; i <= n; i++)
log[i] = log[i / 2] + 1;
for (int i = 1; i < t.size(); i++)
for (int j = 0; j < n - (1 << i) + 1; j++)
t[i][j] = f(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
}
// returns f(a[l..r]) in O(1) time
T get(int l, int r) {
int h = log[r - l + 1];
return f(t[h][l], t[h][r - (1 << h) + 1]);
}
};
long long min_total_length(std::vector<i32> r, std::vector<i32> b) {
vec<pair<int, int>> points;
vec<vec<int>> cords(2, vec<int>());
for (int i: r) {
points.emplace_back(i, 0);
cords[0].emplace_back(i);
}
for (int i: b) {
points.emplace_back(i, 1);
cords[1].emplace_back(i);
}
sort(cords[0].begin(), cords[0].end());
sort(cords[1].begin(), cords[1].end());
sort(points.begin(), points.end());
int n = points.size();
vec<vec<int>> groups;
for (int i = 0; i < n; i++) {
if (i == 0 || points[i].second != points[i - 1].second) {
groups.emplace_back();
}
groups.back().emplace_back(points[i].first);
}
int m = groups.size();
vec<vec<int>> dp(m);
vec<pair<int, int>> prev;
prev = {{0, groups[0].size()}};
for (int t: groups[0]) {
prev[0].first += groups[0].back() - t;
}
prev.emplace_back(inf, inf);
SparseTable stmin1(prev.begin(), prev.end(),
[](const pair<int, int> &a, const pair<int, int> &b) {
return a.first < b.first ? a : b;
});
SparseTable stmin2(prev.begin(), prev.end(),
[](const pair<int, int> &a, const pair<int, int> &b) {
return a.first < b.first ? a : b;
});
for (int i = 1; i < m; i++) {
dp[i].resize(groups[i].size() + 1, inf);
int d = groups[i].front() - groups[i - 1].back();
int T = 0;
{
chmin(dp[i][0], prev.back().first);
}
for (int j = 1; j < dp[i].size(); j++) {
T += groups[i][j - 1] - groups[i][0];
dp[i][j] = inf;
if (i == 1) {
for (int k = 0; k < prev.size() - 1; k++) {
int cost = prev[k].first + T + d * (max(j, (int) prev[k].second));
chmin(dp[i][j], cost);
}
continue;
}
// var1
{
int L = max((int) prev.size() - j, 0LL);
int R = prev.size() - 1;
if (L <= R)
dp[i][j] = stmin1.get(L, R).first + T + d * j;
}
{
int L = 0;
int R = max((int) prev.size() - j, 0LL) - 1;
if(L <= R){
chmin(dp[i][j], stmin2.get(L, R).first + T);
}
}
//
// for (int k = 0; k < max((int) prev.size() - j, 0LL); k++) {
// int cost = prev[k].first + T + d * (max(j, (int) prev[k].second));
// chmin(dp[i][j], cost);
// }
}
vec<pair<int, int>> new_prev;
new_prev.emplace_back(dp[i].back(), 0);
int P = 0;
for (int j = dp[i].size() - 2; j >= 0; j--) {
P += groups[i].back() - groups[i][j];
new_prev.emplace_back(dp[i][j] + P, dp[i].size() - j - 1);
}
reverse(new_prev.begin(), new_prev.end());
prev = new_prev;
stmin1 = SparseTable(prev.begin(), prev.end(),
[](const pair<int, int> &a, const pair<int, int> &b) {
return a.first < b.first ? a : b;
});
vec<pair<int, int>> tprev = new_prev;
int td = 0;
if (i != m - 1) {
td = groups[i + 1].front() - groups[i].back();
}
for (auto &p: tprev) {
p.first += td * p.second;
}
stmin2 = SparseTable(tprev.begin(), tprev.end(),
[](const pair<int, int> &a, const pair<int, int> &b) {
return a.first < b.first ? a : b;
});
}
return dp[m - 1].back();
}
