#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <ll, ll>
#define sz(x) (int)((x).size())
const int N = 2e6 + 11;
const ll INF64 = 3e18 + 1;
ll min_total_length(vector<int> red, vector<int> blue){
vector<ll>a, b;
vector<pi>v;
for(auto it : red){
v.pb({it, 0});
}
for(auto it : blue){
v.pb({it, 1});
}
sort(all(v));
for(auto it : v){
b.push_back(it.ff);
a.push_back(it.ss);
}
vector<ll>close(sz(v) + 5, 0);
vector<ll>match(sz(v) + 5, -1);
vector<ll>matchval(sz(v) + 5, 0);
int n = sz(v);
for(int i = 0; i < n; i++){
int j = i;
while (j + 1 < n && a[j + 1] == a[i])j++; //block of type a[i]
for (int k = i; k <= j; k++){
close[k] = min(i ? b[k] - b[i - 1] : INF64, j + 1 < n ? b[j + 1] - b[k] : INF64);
//close[k] - distance from the closest block of different color
}
i = j;
}
for(int i = 1; i < n; i++){
if(a[i] == a[i - 1])continue;
for(int l = i - 1, r = i; (l >= 0 && r < n && a[l] == a[i - 1] && a[r] == a[i]); l--, r++){
match[r] = l;
matchval[r] = b[r] - b[l];
if(r > i){
matchval[r] += matchval[r - 1]; //if the block has the size larger than 1
}
}
}
vector<ll>dp(n + 5, 0);
dp[0] = close[0];
for(int i = 1; i < n; i++){
dp[i] = dp[i - 1] + close[i];
if(match[i] == -1)continue;
ll DP = (match[i] ? dp[match[i] - 1] : 0);
DP += matchval[i];
dp[i] = min(dp[i], DP);
}
return dp[n - 1];
}
