#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long min_total_length(vector<int> r, vector<int> b) {
vector<pair<int, int>> vpii;
for (auto a : r)
vpii.emplace_back(a, 0);
for (auto a : b)
vpii.emplace_back(a, 1);
sort(vpii.begin(), vpii.end());
vector<ll> qsum(vpii.size());
qsum[0] = vpii[0].first;
for (int i = 1; i < vpii.size(); i++)
qsum[i] = qsum[i - 1] + vpii[i].first;
auto qry = [&](int l, int r) {
if (l == 0)
return qsum[r];
return qsum[r] - qsum[l - 1];
};
vector<ll> dp(vpii.size(), LLONG_MAX);
auto matching = [&](int i1, int i2, int i3, int i4) {
int n = (i2 - i1 + 1), m = (i4 - i3 + 1);
ll bef;
if (i1 == 0)
bef = 0;
else {
bef = min(dp[i1 - 1], dp[i1]);
}
if (bef == LLONG_MAX)
return LLONG_MAX;
if (n < m) {
ll k = m - n;
return qry(i3, i4) - qry(i1, i2) - k * vpii[i2].first + bef;
} else {
ll k = n - m;
return qry(i3, i4) - qry(i1, i2) + k * vpii[i3].first + bef;
}
};
int in0 = 0, in1 = 0;
for (int i = 0; i < vpii.size(); i++)
if (vpii[i].second != vpii[0].second &&
(i + 1 == vpii.size() || vpii[i].second != vpii[i + 1].second)) {
in1 = i;
break;
}
vector<array<int, 3>> vai3;
vai3.push_back({vpii[0].second, 0, 0});
for (int i = 1; i < vpii.size(); i++)
if (vai3.back()[0] == vpii[i].second) {
vai3.back()[2]++;
} else {
vai3.push_back({vpii[i].second, i, i});
}
// for (auto [a, b, c] : vai3) {
// cout << a << ' ' << b << ' ' << c << "\n";
// }
// cout << "\n";
for (int i = 1; i < vai3.size(); i++) {
int in0 = vai3[i - 1][2];
for (int j = vai3[i][1]; j <= vai3[i][2]; j++) {
while (in0 > vai3[i - 1][1] &&
matching(in0 - 1, vai3[i - 1][2], vai3[i][1], j) <=
matching(in0, vai3[i - 1][2], vai3[i][1], j)) {
in0--;
}
dp[j] = matching(in0, vai3[i - 1][2], vai3[i][1], j);
// cout << in0 << " " << j << " " << dp[j] << "\n";
}
}
return dp.back();
}
