#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f1r(i, a, b) for (int (i) = (a); (i) < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define sz(x) (int) (x).size()
#define all(v) (v).begin(), (v).end()
//#ifdef LOCAL
//#define dbg(...) 17;
//#else
//#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
//#endif
#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
long long min_total_length(std::vector<int> r, std::vector<int> b) {
ll ans = 0;
int sz = sz(r) + sz(b);
vector<pair<ll, ll>> pts;
for (ll x : r) pts.eb(x, 0);
for (ll x : b) pts.eb(x, 1);
sort(all(pts));
vector<pair<int, int>> ivals;
int it1 = 0;
int it2 = 0;
while (it1 != sz) {
while (it2 != sz - 1 && pts[it1].s == pts[it2 + 1].s) it2++;
ivals.eb(it1, it2);
it1 = ++it2;
}
vector<ll> pre(sz);
for (int i = 0; i < sz; i++) {
if (i == 0) pre[i] = pts[i].f;
else pre[i] = pre[i-1] + pts[i].f;
}
auto sum = [&](int l, int r) -> ll {
return pre[r] - (l ? pre[l - 1] : 0);
};
const ll INF = 1e18;
vector<ll> dp(sz, INF);
dbg(ivals);
// last thing we've finished
for (int ival = 1; ival < sz(ivals); ival++) {
// previous interval
int pl = ivals[ival - 1].f;
int pr = ivals[ival - 1].s;
for (int i = pr - 1; i >= max(pl - 1, 0); i--) dp[i] = min(dp[i], dp[i + 1]);
int len = pr - pl + 1;
// current interval
int l = ivals[ival].f;
int r = ivals[ival].s;
ll gap = pts[l].f - pts[pr].f;
vector<ll> pref(len + 1);
// if we use at most i of the previous run
vector<ll> suf(len + 1);
// use at least i of the previous run
for (int i = 0; i <= len; i++) {
int hi = pr;
int lo = pr - i + 1;
if (i == 0) pref[i] = INF;
else {
ll add = pts[hi].f * (hi - lo + 1) - sum(lo, hi);
// new thing added
ll bef = (lo ? dp[lo - 1] : 0);
// then what you have to add before
pref[i] = min(pref[i - 1], add + bef);
}
}
for (int i = len; i >= 0; i--) {
int hi = pr;
int lo = pr - i + 1;
if (i == 0) suf[i] = suf[i + 1]; // there's nothing to do here
else if (i == len) {
ll add = pts[hi].f * (hi - lo + 1) - sum(lo, hi) + i * gap;
// how much you're gonna have to add
ll bef = (lo ? dp[lo - 1] : 0);
// how much stuff there is before
suf[i] = add + bef;
} else {
ll add = pts[hi].f * (hi - lo + 1) - sum(lo, hi) + i * gap;
ll bef = (lo ? dp[lo - 1] : 0);
suf[i] = min(suf[i + 1], add + bef);
}
}
// dbg(pre);
// dbg(suf);
for (int i = l; i <= r; i++) {
ll add = sum(l, i) - pts[l].f * (i - l + 1);
// how much you'll add with your new run
int use = i - l + 1;
ll add_gap = use * gap;
dbg(add, l, i, pre);
dp[i] = min(dp[i], pref[min(use, sz(pref) - 1)] + add + add_gap);
if (use < sz(suf)) dp[i] = min(dp[i], suf[use] + add);
}
}
dbg(pts);
dbg(dp);
return dp[sz - 1];
}
