#include "wiring.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10;
const long long inf = 1e18;
int a[N] , col[N] , n;
long long dp[N];
void Solve(int id)
{
int las1 = 1 , las2 = 1 , cnt1 = 0 , cnt2 = 0;
for(int i = id ; i > 0 ; i--)
{
if(col[i] != col[id])
{
las1 = i + 1;
break;
}
cnt1++;
}
for(int i = las1 - 1 ; i > 0 ; i--)
{
if(col[i] != col[las1 - 1])
{
las2 = i + 1;
break;
}
cnt2++;
}
//cout << id << " " << cnt1 << " " << las1 << " " << cnt2 << " " << las2 << endl;
if(cnt2 == 0)
{
dp[id] = inf;
return;
}
if(cnt1 >= cnt2)
{
dp[id] = min(dp[las2 - 1] , dp[las2]);
for(int i = id ; i >= las2 ; i--)
dp[id] += (col[i] == col[id] ? a[i] : -a[i]);
dp[id] -= 1LL * (cnt1 - cnt2) * a[las1 - 1];
return;
}
for(int i = 0 ; i < cnt1 ; i++)
{
dp[id] += (a[id - i] - a[las1 - 1 - i]);
}
long long val = inf , sum = 0;
for(int i = las1 - cnt1 - 1 ; i >= las2 ; i--)
{
val = min(val , sum + dp[i]);
sum += (a[las1] - a[i]);
}
val = min(val , sum + dp[las2 - 1]);
dp[id] += val;
return;
}
long long min_total_length(vector<int> r, vector<int> b) {
n = r.size() + b.size();
vector <pair<int , int>> vec;
for(auto u : r)
vec.push_back({u , 0});
for(auto u : b)
vec.push_back({u , 1});
sort(vec.begin() , vec.end());
for(int i = 1 ; i <= n ; i++)
{
a[i] = vec[i - 1].F;
col[i] = vec[i - 1].S;
}
dp[0] = 0;
for(int i = 1 ; i <= n ; i++)
Solve(i);
return dp[n];
}
