#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll MAXN = 1e6 + 10;
const ll INF = 1e15 + 10;
int n;
ll dp[MAXN], ps[MAXN], len[MAXN], f[MAXN], ps_f[MAXN];
namespace segment {
ll sg[MAXN];
void update(int ind, ll val, int l = 1, int r = n, int v = 1) {
if (l == r) sg[v] = val;
else {
int mid = (l + r) >> 1;
if (ind <= mid) update(ind, val, l, mid, v << 1);
else update(ind, val, mid + 1, r, v << 1 | 1);
sg[v] = min(sg[v << 1], sg[v << 1 | 1]);
}
}
ll query(int ql, int qr, int l = 1, int r = n, int v = 1) {
if (ql > r || qr < l) return INF;
if (ql <= l && qr >= r) return sg[v];
int mid = (l + r) >> 1;
return min(query(ql, qr, l, mid, v << 1),
query(ql, qr, mid + 1, r, v << 1 | 1));
}
};
ll min_total_length(vector<int> r, vector<int> b) {
vector<pll> vec;
vec.push_back({-1, -1});
for (int i = 0; i < int(r.size()); i++) vec.push_back({r[i], 0});
for (int i = 0; i < int(b.size()); i++) vec.push_back({b[i], 1});
sort(all(vec));
dp[0] = 0;
int lst[2] = {0, 0};
n = int(vec.size()) - 1;
for (int i = 1; i <= n; i++) {
auto [x, t] = vec[i];
lst[t] = i;
ps[i] = ps[i - 1] + x;
len[i] = (t == vec[i - 1].Y ? len[i - 1] + 1 : 1);
int ind = lst[t ^ 1];
int y = vec[ind].X;
dp[i] = INF;
if (ind != 0) {
dp[i] = dp[i - 1] + x - y;
if (len[i] <= len[ind]) {
ll s1 = ps[i] - ps[ind], s2 = ps[ind] - (ps[ind - len[i]]);
dp[i] = min(dp[i], dp[ind - len[i]] + s1 - s2);
int l = ind - len[ind] + 1, r = ind - len[i];
if (l <= r)
dp[i] = min(dp[i], s1 - s2 + segment::query(l, r) + ps_f[r]);
}
}
if (i < n && vec[i + 1].Y != t) {
for (int j = i; j > i - len[i]; j--) {
f[j] = vec[i + 1].X - vec[j].X;
}
ps_f[i - len[i]] = 0;
for (int j = i - len[i] + 1; j <= i; j++) {
ps_f[j] = ps_f[j - 1] + f[j];
segment::update(j, dp[j - 1] - ps_f[j - 1]);
}
}
debug(dp[i])
}
return dp[n];
}
