#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
int N = r.size() + b.size();
int ridx = 0, bidx = 0;
vector<int> pos = {0}, col = {0};
while (ridx < r.size() || bidx < b.size()) {
if (bidx == b.size()) {
pos.push_back(r[ridx]);
col.push_back(0);
ridx++;
} else if (ridx == r.size()) {
pos.push_back(b[bidx]);
col.push_back(1);
bidx++;
} else if (r[ridx] < b[bidx]) {
pos.push_back(r[ridx]);
col.push_back(0);
ridx++;
} else {
pos.push_back(b[bidx]);
col.push_back(1);
bidx++;
}
}
vector<pair<int, int>> seg;
for (int i = 1; i <= N; ) {
int j = i;
while (j <= N && col[i] == col[j]) {
j++;
}
seg.push_back(make_pair(i, j - 1));
i = j;
}
vector<long long> pre(N + 1);
for (int i = 1; i <= N; i++) {
pre[i] = pre[i - 1] + pos[i];
}
for (int i = 0; i < seg[1].first - seg[0].first; i++) {
// cerr << " ";
}
vector<long long> dp(N + 1, (long long)1e18);
for (int sid = 1; sid < seg.size(); sid++) {
int clb = seg[sid].first, crb = seg[sid].second;
int plb = seg[sid - 1].first, prb = seg[sid - 1].second;
int opt = prb;
for (int c = clb; c <= crb; c++) {
int psz = prb - plb + 1, csz = c - clb + 1;
long long sum = 0;
sum += pre[c] - pre[clb - 1];
sum -= pre[prb] - pre[plb - 1];
if (psz <= csz) {
sum -= (long long)pos[prb] * (csz - psz);
} else {
sum += (long long)pos[clb] * (psz - csz);
}
int bst = plb;
for (int p = plb; p <= opt; p++) {
int i = p - plb;
long long cur = (sid == 1 ? 0 : min(dp[p - 1], dp[p]));
if (cur + sum < dp[c]) {
bst = p;
}
dp[c] = min(dp[c], cur + sum);
sum += pos[plb + i];
if (psz - i > csz) {
sum -= pos[clb];
} else {
sum -= pos[prb];
}
if (sid == 1) {
break;
}
}
opt = bst;
// cerr << setw(2) << opt << ' ';
}
}
// // cerr << '\n';
for (int i = 1; i <= N; i++) {
// cerr << ' ' << col[i] << ' ';
}
// cerr << '\n';
for (int i = 1; i <= N; i++) {
if (dp[i] == 1e18) {
// cerr << "-1 ";
} else {
// cerr << setw(2) << dp[i] << ' ';
}
}
// cerr << "\n---\n";
return dp[N];
}
