// M
#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long ll;
const int N = 100055 * 2;
int n;
ll dp[N], dpt[N], dps[N], Collapse[N];
pair < int , int > A[N];
vector < int > V[N];
long long min_total_length(vector < int > _R, vector < int > _B)
{
for (int i : _R)
A[++ n] = {i, 0};
for (int i : _B)
A[++ n] = {i, 1};
sort(A + 1, A + n + 1);
int ts = 0;
for (int i = 1; i <= n; i ++)
{
int r = i;
while (r <= n && A[i].second == A[r].second)
r ++;
++ ts;
for (int j = i; j < r; j ++)
V[ts].push_back(A[j].first);
i = r - 1;
}
n = ts;
memset(dp, 63, sizeof(dp));
dp[(int)V[1].size()] = 0;
for (int i : V[1])
dp[(int)V[1].size()] += V[2][0] - i;
V[n + 1].push_back((ll)(2e9));
for (int h = 2; h <= n; h ++)
{
vector < int > &vec = V[h];
int sz = (int)vec.size();
for (int i = 0; i <= sz; i ++)
dpt[i] = (ll)(1e18);
int mxsz = max(sz, (int)V[h - 1].size()) + 5;
fill(dps, dps + mxsz, (ll)(1e18));
for (int i = (int)V[h - 1].size(); i >= 0; i --)
dps[i] = min(dp[i], dps[i + 1]);
for (int i = 1; i <= sz; i ++)
Collapse[i] = Collapse[i - 1] + vec[i - 1] - vec[0];
// We'll be doing it backwards ...
for (int i = 0; i <= sz; i ++)
dpt[i] = min(dpt[i], dps[i] + Collapse[i]);
ll df = vec[0] - V[h - 1].back();
ll Mn = 1e18;
for (int i = 0; i <= sz; i ++)
{
dpt[i] = min(dpt[i], Mn + Collapse[i] + df * i);
Mn = min(Mn, dp[i] - df * i);
}
reverse(dpt, dpt + sz + 1);
fill(dp, dp + mxsz, (ll)(1e18));
for (int i = 0; i <= sz; i ++)
dp[i] = dpt[i];
ll val = 0;
for (int i = 1; i <= sz; i ++)
{
val += V[h + 1][0] - vec[sz - i];
dp[i] += val;
}
}
return dp[0];
}
