#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll min_total_length(std::vector<int> re, std::vector<int> bl)
{
int n = re.size() + bl.size();
vector < pair < int , int > > v;
for (int x : re) v.emplace_back(x, 0);
for (int x : bl) v.emplace_back(x, 1);
sort(v.begin(), v.end());
ll cur = 0;
vector < ll > dp(n, 1ll<<60), last(n);
last[0] = -1;
vector < ll > a(n, 0), b(n, 0);
for (int i = 1; i < n; i++)
{
auto [x, t] = v[i];
if (v[i-1].second == t)
{
last[i] = last[i-1];
cur += x - v[last[i]+1].first;
}
else
{
cur = 0;
last[i] = i-1;
a[i-1] = 0;
b[i-1] = x - v[i-1].first;
for (int j = i-2; j > last[i-1]; j--)
{
a[j] = a[j+1] + v[i-1].first - v[j].first;
b[j] = b[j+1] + v[i].first - v[j].first;
}
//cerr << " A:";
//for (auto x : a) cerr << x << " "; cerr << "\n";
//cerr << " B:";
//for (auto x : b) cerr << x << " "; cerr << "\n";
for (int j = i-1; j > max(last[i-1], 0ll); j--)
{
a[j] += min(dp[j-1], dp[j]);
b[j] += min(dp[j-1], dp[j]);
}
//cerr << "DA:";
//for (auto x : a) cerr << x << " "; cerr << "\n";
//cerr << "DB:";
//for (auto x : b) cerr << x << " "; cerr << "\n";
for (int j = i-2; j > last[i-1]; j--)
a[j] = min(a[j], a[j+1]);
for (int j = last[i-1]+2; j < i; j++)
b[j] = min(b[j], b[j-1]);
//cerr << "MA:";
//for (auto x : a) cerr << x << " "; cerr << "\n";
//cerr << "MB:";
//for (auto x : b) cerr << x << " "; cerr << "\n";
}
if (last[i] == -1) continue;
int len = i - last[i];
ll gap = v[last[i]+1].first - v[last[i]].first;
int split = max(last[last[i]], last[i]-len)+1;
dp[i] = a[split] + gap*len;
if (split > last[last[i]]+1) dp[i] = min(dp[i], b[split-1]);
dp[i] += cur;
//cerr << i << ":" << dp[i] << "\n";
}
return dp[n-1];
}
