#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T>
struct segment_tree {
int n;
vector<T> s;
T (*f)(T, T);
T e;
segment_tree(int _n, T(*_f)(T, T), T _e) : f(_f), e(_e) {
n = 2 << __lg(_n);
s.resize(2 * n - 1, e);
}
void modify(int p, int l, int r, int x, T v) {
if (r - l == 1) {
s[p] = v;
return;
}
int m = (l + r + 1) / 2;
if (x < m) {
modify(p * 2 + 1, l, m, x, v);
} else {
modify(p * 2 + 2, m, r, x, v);
}
s[p] = f(s[p * 2 + 1], s[p * 2 + 2]);
}
void modify(int x, T v) {
modify(0, 0, n, x, v);
}
T range_query(int p, int l, int r, int L, int R) {
if (R <= l || r <= L) {
return e;
}
if (L <= l && r <= R) {
return s[p];
}
int m = (l + r + 1) / 2;
return f(range_query(p * 2 + 1, l, m, L, R), range_query(p * 2 + 2, m, r, L, R));
}
T range_query(int l, int r) {
return range_query(0, 0, n, l, r);
}
};
pair<ll, ll> fmin(pair<ll, ll> x, pair<ll, ll> y) {
return {min(x.first, y.first), min(x.second, y.second)};
}
constexpr ll inf = 1E16;
long long min_total_length(vector<int> R, vector<int> B) {
int N = R.size();
int M = B.size();
vector<array<int, 2>> T;
for (int x : R) {
T.push_back({x, 0});
}
for (int x : B) {
T.push_back({x, 1});
}
sort(T.begin(), T.end());
vector<ll> pfs(N + M + 1);
for (int i = 0; i < N + M; i++) {
pfs[i + 1] = pfs[i] + T[i][0];
}
vector<int> e(N + M + 1, -1);
for (int i = N + M - 2; i >= 0; i--) {
if (T[i][1] == T[i + 1][1]) {
e[i] = e[i + 1];
} else {
e[i] = i + 1;
}
}
vector<int> d(N + M, -1);
segment_tree<pair<ll, ll>> st(N + M, fmin, {inf, inf});
vector<ll> dp(N + M + 1, inf);
st.modify(0, {0, 0});
dp[0] = 0;
for (int i = 0; i < N + M; i++) {
if (i > 0) {
if (T[i][1] == T[i - 1][1]) {
d[i] = d[i - 1];
} else {
d[i] = i - 1;
}
}
if (d[i] != -1) {
int j = d[i];
dp[i + 1] = min(dp[i + 1], dp[j + 1] + (pfs[i + 1] - pfs[j + 1]) - 1LL * (i - j) * T[j][0]);
int k = 2 * j + 1 - i;
if (d[j] + 1 <= k) {
dp[i + 1] = min(dp[i + 1], st.range_query(d[j] + 1, min(k, j) + 1).first + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j + 1][0]));
}
if (k < j) {
dp[i + 1] = min(dp[i + 1], st.range_query(max(k, d[j]) + 1, j + 1).second + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j][0]));
}
if (e[i + 1] != -1) {
st.modify(i + 1, {dp[i + 1] + pfs[i + 1] - 1LL * (i + 1) * T[e[i + 1]][0], dp[i + 1] + pfs[i + 1] - 1LL * (i + 1) * T[e[i + 1] - 1][0]});
}
}
}
return dp[N + M];
}
