#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
long long INF = (long long)1e10;
vector<pair<int, int>> v;
vector<long long> ossz;
long long ertek(int l, int m, int r){
long long ossz1 = ossz[m-1]-ossz[l-1], ossz2 = ossz[r]-ossz[m-1];
if(m-l < r-m+1)
ossz1 += (long long)v[m-1].first*(r-2*m+l+1);
else
ossz2 += (long long)v[m].first*(2*m-r-l-1);
return ossz2 - ossz1;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
v.resize(r.size()+b.size()+1);
int n = 0;
for(int x : r)
v[n++] = make_pair(x, 0);
for(int x : b)
v[n++] = make_pair(x, 1);
if(r[0] < b[0])
v[n++] = make_pair(-1, 0);
else
v[n++] = make_pair(-1, 1);
sort(v.begin(), v.end());
ossz.resize(n);
ossz[0] = v[0].first;
for(int i = 1; i < n; i++)
ossz[i] = ossz[i-1] + (long long)v[i].first;
vector<long long> dp(n, INF);
dp[0] = 0ll;
for(int i = 1; i < n && v[i].second == v[0].second; i++)
dp[i] = (long long)i*INF;
int lastr = -1, lastb = -1, j = -1;
for(int i = 1; i < n; i++){
if(v[i].second == 0 && (lastr == -1 || v[i-1].second != 0)){
lastr = i;
j = lastr-1;
}else if(v[i].second == 1 && (lastb == -1 || v[i-1].second != 1)){
lastb = i;
j = lastb-1;
}
if(lastr == -1 || lastb == -1)
continue;
while(j > min(lastb, lastr) && ertek(j, max(lastb, lastr), i)+dp[j-1] > ertek(j-1, max(lastb, lastr), i)+dp[j-2])
j--;
dp[i] = ertek(j, max(lastb, lastr), i)+dp[j-1];
}
return dp[n-1];
}
