#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
LL min_total_length(vector<int> r, vector<int> b)
{
int N = r.size(), M = b.size();
int K = N + M;
vector<pii> v;
for(auto &x: r) v.emplace_back(x, 0);
for(auto &x: b) v.emplace_back(x, 1);
sort(begin(v), end(v));
vector<LL> sum;
sum.resize(K + 5);
sum[0] = v[0].first;
for(int i = 1; i < K; i++) sum[i] = sum[i - 1] + v[i].first;
vector<LL> dp;
dp.resize(K + 5);
multiset<LL> lessK, moreK;
int st = -1, lstst = -1, lstdr = -1, col = -1;
for(int i = 0; i < K; i++)
{
if(col != v[i].second)
{
lstst = st, lstdr = i - 1;
st = i, col = v[i].second;
lessK.clear(), moreK.clear();
if(lstst != -1)
{
LL cost = 0LL;
for(int i = lstdr; i >= lstst; i--)
{
cost += v[st].first - v[i].first;
LL dpcost = cost;
if(i > 0) dpcost += dp[i - 1];
lessK.insert(dpcost);
}
}
}
dp[i] = 1LL << 60;
if(lstst == -1) continue;
LL sumRight = (sum[i] - sum[st]) - 1LL * (i - st) * v[st].first;
int lgt = (i - st + 1);
if(!lessK.empty())
{
LL cost = sumRight + (*lessK.begin());
dp[i] = min(dp[i], cost);
}
if(!moreK.empty())
{
LL cost = sumRight + 1LL * lgt * (v[st].first - v[lstdr].first) + (*moreK.begin());
dp[i] = min(dp[i], cost);
}
if(lstdr - lstst + 1 >= lgt)
{
LL sumLeft = 1LL * lgt * v[lstdr].first - (sum[lstdr] - sum[lstdr - lgt + 1] + v[lstdr - lgt + 1].first);
LL cost = sumLeft;
if(lstdr - lgt + 1 > 0) cost += dp[lstdr - lgt];
moreK.insert(cost);
cost += 1LL * lgt * (v[st].first - v[lstdr].first);
lessK.erase( lessK.find(cost) );
}
}
return dp[K - 1];
}
