#include "wiring.h"
#include <vector>
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<long long> pre(N + 1);
for (int i = 1; i <= N; i++) {
pre[i] = pre[i - 1] + pos[i];
}
vector<long long> cur(N + 2, (long long)1e18);
vector<long long> dp(N + 1, (long long)1e18);
for (int idx = 1; idx <= N; ) {
int clb = idx, crb = idx;
while (crb <= N && col[crb] == col[clb]) {
crb++;
}
idx = crb;
crb--;
if (clb == 1) {
continue;
}
int prb = clb - 1, plb = prb;
while (plb >= 1 && col[plb] == col[prb]) {
plb--;
}
plb++;
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);
}
if (plb == 1) {
long long cur = 1;
dp[c] = min(dp[c], sum);
} else {
for (int i = 0; i < psz; i++) {
int p = plb + i;
dp[c] = min(dp[c], cur[p] + sum);
sum += pos[p];
if (psz - i > csz) {
sum -= pos[clb];
} else {
sum -= pos[prb];
}
}
}
cur[c] = min(cur[c], dp[c]);
cur[c + 1] = min(cur[c + 1], dp[c]);
}
}
return dp[N];
}
