#pragma GCC optimize("O3")
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, ans;
vector<int> fullList;
unordered_map<int, bool> isRed, isBlue;
vector<vector<int>> segments;
vector<vector<int>> prefixR;
vector<vector<int>> prefixL;
int calcWire(int s, int l, int r) {
int res = 0;
res += prefixL[s][l];
res += (segments[s].size()-l) * (segments[s+1][0]-segments[s].back());
res += prefixR[s+1][r];
res += (r+1) * (segments[s+1][0]-segments[s].back());
res -= min((int)segments[s].size()-l, r+1)*(segments[s+1][0]-segments[s].back());
return res;
}
int shash(int a, int b) {
return a*1000000 + b;
}
unordered_map<int, int> dp;
long long min_total_length(vector<signed> r, vector<signed> b) {
dp.reserve(32768); dp.max_load_factor(0.25);
n = r.size();
m = b.size();
fullList.resize(n+m);
merge(r.begin(), r.end(), b.begin(), b.end(), fullList.begin());
for(auto x: r)
isRed[x]=1;
for(auto x: b)
isBlue[x]=1;
for(int i = 0; i < m+n; i++) {
if(i==0 || isRed[fullList[i]] != isRed[fullList[i-1]]) {
segments.push_back(vector<int>(0));
prefixL.push_back(vector<int>(0));
prefixR.push_back(vector<int>(0));
segments.back().push_back(fullList[i]);
} else {
segments.back().push_back(fullList[i]);
}
}
for(int s = 0; s < segments.size(); s++) {
prefixR[s].push_back(0);
for(int i = 1; i < segments[s].size(); i++)
prefixR[s].push_back(prefixR[s][i-1]+segments[s][i]-segments[s][0]);
reverse(segments[s].begin(), segments[s].end());
prefixL[s].push_back(0);
for(int i = 1; i < segments[s].size(); i++)
prefixL[s].push_back(prefixL[s][i-1]+segments[s][0]-segments[s][i]);
reverse(prefixL[s].begin(), prefixL[s].end());
reverse(segments[s].begin(), segments[s].end());
}
for(int j = 0; j < segments[1].size(); j++) {
dp[shash(1,j)] = calcWire(0, 0, j);
}
for(int s = 2; s < segments.size(); s++) {
for(int i = 0; i < segments[s].size(); i++) {
dp[shash(s, i)] = dp[shash(s-1, 0)] + calcWire(s-1, 0, i);
if(dp[shash(s-2, segments[s-2].size()-1)] != 0)
dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-2, segments[s-2].size()-1)] + calcWire(s-1, 0, i));
int lo = 1, hi = max(1ll,(int)segments[s-1].size()-1), j, m1, m2, r1, r2;
while(lo+1 < hi) {
m1 = (lo+lo+hi)/3;
r1 = dp[shash(s-1, m1-1)] + calcWire(s-1, m1, i);
m2 = (lo+hi+hi)/3;
r2 = dp[shash(s-1, m2-1)] + calcWire(s-1, m2, i);
if(r1==r2)
lo = m1, hi = m2;
else if(r1 < r2)
hi = m2-1;
else
lo = m1+1;
}
dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-1, lo-1)] + calcWire(s-1, lo, i));
dp[shash(s, i)] = min(dp[shash(s, i)], dp[shash(s-1, hi-1)] + calcWire(s-1, hi, i));
// cerr << s << " " << i << ": " << dp[shash(s, i)] << endl;
}
}
return dp[shash(segments.size()-1, segments.back().size()-1)];
if(segments.size() == 2)
return calcWire(0, 0, m-1);
return -1;
}
