#include "wiring.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
struct Event {
bool red;
ll t;
bool operator <(const Event& o) const {
return t < o.t;
}
};
struct Val {
ll i, val;
bool operator <(const Val& o) const {
return val < o.val;
}
};
const ll N = 2e5 + 10, INF = 7e12;
vector<Event> e;
ll n, m, t, sum = 0, pre[N], dist[N];
void initDist() {
ll prec[2] = {-INF, -INF};
for(int i = 0; i < t; i++) {
if(e[i].red) {
pre[i] = prec[1];
prec[0] = e[i].t;
} else {
pre[i] = prec[0];
prec[1] = e[i].t;
}
dist[i] = e[i].t - pre[i];
}
prec[0] = INF;
prec[1] = INF;
for(int i = t-1; i > -1; i--) {
if(e[i].red) {
prec[0] = e[i].t;
dist[i] = min(dist[i], prec[1] - e[i].t);
} else {
prec[1] = e[i].t;
dist[i] = min(dist[i], prec[0] - e[i].t);
}
}
}
ll min_total_length(vector<int> r, vector<int> b) {
n = r.size();
m = b.size();
t = n + m;
for(int i : r)
e.push_back({true, i});
for(int i : b)
e.push_back({false, i});
sort(e.begin(), e.end());
initDist();
set<Val> blue, red;
for(int i = 0; i < t; i++) {
if(e[i].red) {
auto it = blue.begin();
while(!blue.empty() && (*it).val < e[i].t) {
sum += (*it).val - e[(*it).i].t;
blue.erase(it);
it = blue.begin();
//cout << "1 " << sum << '\n';
}
if(blue.empty()) {
red.insert({i, 2*e[i].t - pre[i]});
} else {
sum += e[i].t - e[(*it).i].t;
blue.erase(it);
//cout << "2 " << sum << '\n';
}
} else {
auto it = red.begin();
while(!red.empty() && (*it).val < e[i].t) {
sum += (*it).val - e[(*it).i].t;
red.erase(it);
it = blue.begin();
//cout << "3 " << sum << '\n';
}
if(red.empty()) {
blue.insert({i, 2*e[i].t - pre[i]});
} else {
sum += e[i].t - e[(*it).i].t;
red.erase(it);
//cout << "4 " << sum << '\n';
}
}
}
for(Val v : red)
sum += dist[v.i];
for(Val v : blue)
sum += dist[v.i];
return sum;
}
