#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pi = pair<int, int>;
const ll INF = 4e18;
ll min_total_length(vi r, vi b) {
if (r[0] > b[0]) swap(r, b);
int n = r.size(), m = b.size();
ll ans = 0;
vector<pi> mhm;
int i = 0, j = 0;
while (i<n && j<m) {
if (r[i] < b[j]) mhm.push_back({0, r[i++]});
else mhm.push_back({1, b[j++]});
}
while (i<n) mhm.push_back({0, r[i++]});
while (j<m) mhm.push_back({1, b[j++]});
vector<ll> dp(n+m+1, INF);
vector<ll> pref(n+m+1, 0); for (int i = 0; i <n+m; i++) pref[i+1] += pref[i] + mhm[i].second;
dp[0] = 0;
int len = 0, prev_len = 0, cur = 0;
for (int i = 1; i <= n+m; i++) {
if (mhm[i-1].first != cur) {prev_len = len, len = 1, cur = 1-cur;}
else len++;
if (prev_len == 0) continue;
for (int j = i-len-prev_len + 1; j <= i-len; j++) {
ll s1 = 0, s2 = 0;
s1 = pref[i-len] - pref[j-1];
s2 = pref[i] - pref[i-len];
// for (int k = j; k <= i-len; k++) s1 += mhm[k-1].second;
// for (int k = i-len+1; k <= i; k++) s2 += mhm[k-1].second;
ll L1 = ((i-len) - (j) + 1), L2 = len;
s1 += max(0LL, L2-L1) * mhm[i-len-1].second;
s2 += max(0LL, L1-L2) * mhm[i-len].second;
dp[i] = min(dp[i], min(dp[j], dp[j-1]) + s2 - s1);
}
}
return dp.back();
}
