#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(std::vector<int> R, std::vector<int> B) {
int n = R.size(), m = B.size();
vector<long long> r = {0}, b = {0};
for (int i : R) r.push_back(i + r.back());
for (int i : B) b.push_back(i + b.back());
vector<pair<int, long long>> p;
for (int i = 0; i < n; i++) p.emplace_back(R[i], i + 1);
for (int i = 0; i < m; i++) p.emplace_back(B[i], -i - 1);
sort(p.begin(), p.end());
vector<int> head(n + m);
auto get = [&](int s, int e)
{
if (p[s].second > 0)
{
long long lr = p[s].second - 1;
long long rr = p[head[e] - 1].second - 1;
long long lb = -p[head[e]].second - 1;
long long rb = -p[e].second - 1;
//cout << lr << ' ' << rr << ' ' << lb << ' ' << rb << '\n';
return (rr - lr + 1) * R[rr] - r[rr + 1] + r[lr] +
b[rb + 1] - b[lb] - (rb - lb + 1) * B[lb] +
max(rr - lr + 1, rb - lb + 1) * (B[lb] - R[rr]);
}
else
{
long long lb = -p[s].second - 1;
long long rb = -p[head[e] - 1].second - 1;
long long lr = p[head[e]].second - 1;
long long rr = p[e].second - 1;
//cout << lr << ' ' << rr << ' ' << lb << ' ' << rb << '\n';
return (rb - lb + 1) * B[rb] - b[rb + 1] + b[lb] +
r[rr + 1] - r[lr] - (rr - lr + 1) * R[lr] +
max(rr - lr + 1, rb - lb + 1) * (R[lr] - B[rb]);
}
};
long long inf = 1e18;
vector<long long> dp(n + m + 1, inf);
dp[0] = 0;
for (int i = 1; i < n + m; i++)
{
head[i] = head[i - 1];
if (p[i].second * p[i - 1].second < 0)
{
int prev = head[i];
head[i] = i;
dp[i + 1] = dp[i] + get(i - 1, i);
for (int j = prev; j < i; j++)
{
dp[i + 1] = min(dp[i + 1], dp[j] + get(j, i));
}
}
else if (head[i])
{
int s = head[head[i] - 1], e = head[i];
if (s == 0) dp[i + 1] = get(0, i);
else if (e - s < 200)
{
for (int j =s; j < e; j++)
{
dp[i + 1] = min(dp[i + 1], min(dp[j], dp[j + 1]) + get(j, i));
}
}
else
{
int low = s, high = e;
while (high - low > 1)
{
int mid = (low + high) / 2;
if (dp[mid] + get(mid, i) <= dp[mid - 1] + get(mid - 1, i)) low = mid;
else high = mid;
}
dp[i + 1] = dp[low] + get(low, i);
}
}
}
return dp[n + m];
}
