#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)
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define sum(x) accumulate(all(x), 0LL)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
const ll INF = 1e18;
vector<vi> buildSegments(const vi &r, const vi &b) {
vector<vi> g;
bool last = false;
const int n = sz(r), m = sz(b);
int i = 0, j = 0;
while (i < n || j < m) {
if (j == m || (i < n && r[i] < b[j])) {
if (g.empty() || last) g.eb();
g.back().pb(r[i++]), last = 0;
} else {
if (g.empty() || !last) g.eb();
g.back().pb(b[j++]), last = 1;
}
}
return g;
}
vll calcDP(const vll &prev, const vi &a, const vi &b) {
const int n = sz(a), m = sz(b);
vll pref(n + 1), suff(n + 1);
ll sum = 0, dist = b.front() - a.back();
forn(i, n + 1) {
pref[i] = prev[n - i] + sum;
suff[i] = pref[i] + i * dist;
if (i < n) sum += a.back() - a[n - 1 - i];
}
forsn(i, 1, n + 1) pref[i] = min(pref[i], pref[i - 1]);
dforn(i, n) suff[i] = min(suff[i], suff[i + 1]);
vll dp(m + 1);
sum = 0;
forn(i, m + 1) {
dp[i] = pref[min(i, n)] + sum + i * dist;
if (i <= n) dp[i] = min(dp[i], suff[i] + sum);
if (i < m) sum += b[i] - b.front();
}
return dp;
}
ll min_total_length(vi r, vi b) {
vector<vi> g = buildSegments(r, b);
assert(sz(g) >= 2);
vll dp(sz(g[0]) + 1, INF);
dp[0] = 0;
forsn(i, 1, sz(g)) dp = calcDP(dp, g[i - 1], g[i]);
return dp.back();
}
