#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];
}
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 psz = prb - plb + 1;
vector<long long> dqb(psz);
for (int i = 0, p = plb; i < psz; i++, p++) {
dqb[i] += min(dp[p - 1], dp[p]);
dqb[i] += pre[p - 1] - pre[plb - 1];
}
vector<long long> dqd(psz);
dqd[0] = dqb[0];
for (int i = 1; i < psz; i++) {
dqd[i] = -dqb[i - 1] + dqb[i];
}
for (int c = clb; c <= crb; c++) {
int 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 (sid == 1) {
dp[c] = sum;
} else {
vector<pair<int, long long>> ops;
dqd[0] += sum, ops.push_back(make_pair(0, sum));
for (int i = 1; i <= psz - csz; i++) {
dqd[i] -= pos[clb], ops.push_back(make_pair(i, -pos[clb]));
}
for (int i = max(0, psz - csz) + 1; i < psz; i++) {
dqd[i] -= pos[prb], ops.push_back(make_pair(i, -pos[prb]));
}
long long cur = 0;
vector<long long> dq(psz);
for (int i = 0; i < psz; i++) {
cur += dqd[i];
dp[c] = min(dp[c], cur);
}
for (auto &[pos, val] : ops) {
dqd[pos] -= val;
}
}
}
}
return dp[N];
}
