#include "wiring.h"
#include <climits>
#include <algorithm>
using namespace std;
bool is_st2(vector<int> r, vector<int> b)
{
return r.back() < b.front();
}
long long solve_st2(vector<int> r, vector<int> b)
{
long ans = 0;
for (int x : r)
ans += r.back() - x;
for (int y : b)
ans += y - b.front();
ans += max(r.size(), b.size()) * (b.front() - r.back());
return ans;
}
long long min_total_length(vector<int> r, vector<int> b)
{
if (is_st2(r, b))
return solve_st2(r, b);
vector<pair<int, bool>> V;
for (auto x : r)
V.emplace_back(x, 0);
for (auto x : b)
V.emplace_back(x, 1);
sort(V.begin(), V.end());
vector<long long> D(V.size() + 1, LLONG_MAX / 2);
D[0] = 0;
for (int i = 0; i < (int)V.size(); i++)
{
bool colour = V[i].second;
long long rsum = V[i].first, rcnt = 1, mid = -1;
int j;
for (j = i - 1; j >= 0; --j)
{
if (colour != V[j].second)
{
rsum -= rcnt * V[j + 1].first;
mid = V[j + 1].first - V[j].first;
D[i + 1] = min(D[i + 1], D[j] + mid * rcnt + rsum);
break;
}
else
{
rcnt++;
rsum += V[j].first;
}
}
if (j <= 0)
continue;
int anchor = V[j].first;
if (V[j - 1].second == colour)
{
for (--j; j >= 0; --j)
{
if (V[j].second != colour)
break;
rsum += anchor - V[j].first;
D[i + 1] = min(D[i + 1], D[j] + mid * rcnt + rsum);
}
}
else
{
long long bsum = V[j].first, bcnt = 1;
for (--j; j >= 0; --j)
{
if (V[j].second == colour)
break;
bsum += V[j].first;
bcnt++;
long long cost = (anchor * bcnt - bsum) + rsum + mid * max(rcnt, bcnt);
D[i + 1] = min(D[i + 1], D[j] + cost);
}
}
}
return D.back();
}
