#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
const ll INF = 1e18;
ll min_total_length(vi r, vi b) {
vector<pair<vi, bool>> groups;
for (int i = 0, j = 0; i < sz(r) || j < sz(b); ) {
if (j >= sz(b) || (i < sz(r) && r[i] < b[j])) {
if (groups.empty() || groups.back().snd) groups.eb(vi{r[i]}, false);
else groups.back().fst.pb(r[i]);
i++;
} else {
if (groups.empty() || !groups.back().snd) groups.eb(vi{b[j]}, true);
else groups.back().fst.pb(b[j]);
j++;
}
}
vll dp(sz(groups[0].fst) + 1, INF);
dp[0] = 0;
forsn(g, 1, sz(groups)) {
auto &pos = groups[g].fst;
auto &prevPos = groups[g - 1].fst;
int n = sz(pos), m = sz(prevPos);
int dist = pos.front() - prevPos.back();
vll suff(m + 1);
suff[m] = 0LL;
dforn(i, m) suff[i] = suff[i + 1] + prevPos.back() - prevPos[i];
vll pref(n + 1);
pref[0] = 0LL;
forn(i, n) pref[i + 1] = pref[i] + pos[i] - pos.front();
vll bestPref(m + 1), bestSuff(m + 1);
forn(i, m + 1) {
bestPref[i] = dp[m - i] + suff[m - i];
bestSuff[i] = dp[m - i] + suff[m - i] + 1LL * i * dist;
}
forsn(i, 1, m + 1) bestPref[i] = min(bestPref[i], bestPref[i - 1]);
dforn(i, m) bestSuff[i] = min(bestSuff[i], bestSuff[i + 1]);
vll newDP(sz(pos) + 1, INF);
forn(i, sz(pos) + 1) {
newDP[i] = pref[i] + 1LL * i * dist + bestPref[min(i, sz(prevPos))];
if (i < sz(prevPos)) newDP[i] = min(newDP[i], pref[i] + bestSuff[i + 1]);
}
dp = newDP;
}
return dp.back();
}
