#include "wiring.h"
//author: erray
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/debug.h"
#else
#define debug(...) (void) 37
#endif
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<vector<int>> gs;
{
vector<int> m;
merge(r.begin(), r.end(), b.begin(), b.end(), back_inserter(m));
int pr = -1, pb = -1;
int last = -1;
for (int i = 0; i < int(m.size()); ++i) {
int next = -1;
if (pr + 1 < int(r.size()) && r[pr + 1] == m[i]) {
++pr;
next = 0;
} else {
++pb;
next = 1;
}
if (next != last) {
gs.push_back({});
}
gs.back().push_back(m[i]);
swap(next, last);
}
}
debug(gs);
const long long inf = (long long) 1e17;
vector<long long> dp(int(gs[0].size()) + 1, inf);
dp[0] = 0;
for (int bi = 1; bi < int(gs.size()); ++bi) {
debug(dp);
auto& v = gs[bi];
auto& prev = gs[bi - 1];
int n = int(v.size());
int m = int(prev.size());
int gap = v[0] - prev.back();
vector<long long> small(n + 1, inf), big(n + 1, inf);
{
long long sum = 0;
for (int i = m - 1; i >= 0; --i) {
sum += prev[m - 1] - prev[i];
int match = m - i;
long long cost = sum + dp[i];
if (match <= n) {
big[match] = min(big[match], cost);
}
match = min(match, n);
small[match] = min(small[match], cost + 1LL * (m - i) * gap);
}
}
vector<long long> new_dp(n + 1);
{
long long mn = inf;
for (int i = 1; i <= n; ++i) {
mn = min(mn, big[i]);
new_dp[i] = mn + 1LL * i * gap;
}
}
{
long long mn = inf;
for (int i = n; i >= 1; --i) {
mn = min(mn, small[i]);
new_dp[i] = min(new_dp[i], mn);
}
}
new_dp[0] = dp[m];
{
long long sum = 0;
for (int i = 1; i <= n; ++i) {
sum += v[i - 1] - v[0];
new_dp[i] += sum;
}
}
swap(dp, new_dp);
for (int i = n; i > 0; --i) {
dp[i - 1] = min(dp[i], dp[i - 1]);
}
}
debug(dp);
return dp.back();
}
