#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);
}
};
ll fmin(ll x, ll y) {
return min(x, y);
}
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);
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<ll> st(N + M, fmin, inf);
vector<ll> dp(N + M + 1, inf);
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) {
continue;
}
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]);
for (int p = d[j] + 1; p <= j; p++) {
int m = min(j - p + 1, i - j);
ll s = 0;
if (j + 1 - p >= i - j) {
s = (pfs[p] - 1LL * p * T[j + 1][0]) + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j + 1][0]);
} else {
s = (pfs[p] - 1LL * p * T[j][0]) + (pfs[i + 1] - 2 * pfs[j + 1] + (2LL * j + 1 - i) * T[j][0]);
}
dp[i + 1] = min(dp[i + 1], dp[p] + s);
}
}
return dp[N + M];
}
