#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
using ll = long long;
const int MAXN = 200005;
const ll INF = (1LL<<60);
ll dp[MAXN];
ll psa[MAXN];
pair<ll,int> dt[MAXN]; // 1-indexed
int N_global; // if you need global elsewhere, but we'll set/reset it
long long min_total_length(vector<int> R, vector<int> B) {
// --- INITIALIZE ---
N_global = 0; // CRITICAL: reset N before filling dt
for (int x : R) dt[++N_global] = {x, 1};
for (int x : B) dt[++N_global] = {x, -1};
sort(dt + 1, dt + 1 + N_global);
// prefix sum of positions
psa[0] = 0;
for (int i = 1; i <= N_global; ++i) psa[i] = psa[i-1] + dt[i].first;
// dp init
for (int i = 0; i <= N_global; ++i) dp[i] = INF;
dp[0] = 0;
// iterate chunks of equal color
int prev = 1; // start index of previous chunk
int l = 1;
while (l <= N_global) {
int r = l;
while (r <= N_global && dt[r].second == dt[l].second) ++r;
// chunk is [l, r) (r is first index after chunk)
// 1) pair elements of this chunk with the next chunk's first element
if (r <= N_global) {
for (int i = l; i < r; ++i) {
// dp[i] can be formed by pairing i with dt[r].first and using dp[i-1]
dp[i] = min(dp[i], dp[i-1] + (dt[r].first - dt[i].first));
}
}
// 2) pair elements of this chunk with previous elements
if (l != 1) {
// Precompute the base term:
// base = min_{k in [prev..l-1]} ( dp[k-1] - (psa[l-1] - psa[k-1]) )
ll base = INF;
for (int k = prev; k <= l-1; ++k) {
base = min(base, dp[k-1] - (psa[l-1] - psa[k-1]));
}
// then for each i in [l, r), extra = base + dt[l-1].first * (i - l + 1)
ll cost = 0; // incremental cost of pairing current chunk elements to dt[l-1].first
for (int i = l; i < r; ++i) {
cost += dt[i].first - dt[l-1].first; // add distance from dt[i] to dt[l-1]
ll extra = base + dt[l-1].first * (i - l + 1);
dp[i] = min(dp[i], cost + extra);
}
}
prev = l;
l = r;
}
// optional: debug print dp values
for (int i = 1; i <= N_global; ++i) {
}
return dp[N_global];
}
