#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
vector<pair<int, int>> all;
for (int i = 0, j = 0; i < n; ++i) {
while (j < m && b[j] < r[i]) {
all.emplace_back(b[j++], 1);
}
all.emplace_back(r[i], -1);
if (i == n - 1) {
while (j < m) {
all.emplace_back(b[j++], 1);
}
}
}
vector<int> pref(n + m + 1, -1);
vector<long long> dp(n + m + 1);
vector<long long> sum(n + m + 1);
int cur = n;
pref[cur] = 0;
for (int i = 0, ptr_r = 0, ptr_b = 0; i < n + m; ++i) {
sum[i + 1] = sum[i] + all[i].first * all[i].second;
cur += all[i].second;
if (all[i].second == -1) {
while (ptr_b < m && b[ptr_b] < all[i].first) {
++ptr_b;
}
if (!ptr_b) {
dp[i + 1] = dp[i] + b[ptr_b] - all[i].first;
} else if (ptr_b == m) {
dp[i + 1] = dp[i] + all[i].first - b[ptr_b - 1];
} else {
dp[i + 1] = dp[i] + min(b[ptr_b] - all[i].first, all[i].first - b[ptr_b - 1]);
}
} else {
while (ptr_r < n && r[ptr_r] < all[i].first) {
++ptr_r;
}
if (!ptr_r) {
dp[i + 1] = dp[i] + r[ptr_r] - all[i].first;
} else if (ptr_r == n) {
dp[i + 1] = dp[i] + all[i].first - r[ptr_r - 1];
} else {
dp[i + 1] = dp[i] + min(r[ptr_r] - all[i].first, all[i].first - r[ptr_r - 1]);
}
}
if (pref[cur] != -1) {
dp[i + 1] = min(dp[i + 1], dp[pref[cur]] + abs(sum[i + 1] - sum[pref[cur]]));
}
pref[cur] = i + 1;
}
return dp[n + m];
}
