#include "wiring.h"
#include <algorithm>
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int brute(vector<signed> r, vector<signed> b) {
int nbRouges = r.size();
int nbBleus = b.size();
vector<vector<int>> dp(nbRouges, vector<int>(nbBleus));
for (int iRouge = 0; iRouge < nbRouges; ++iRouge)
for (int iBleu = 0; iBleu < nbBleus; ++iBleu) {
dp[iRouge][iBleu] = abs(r[iRouge] - b[iBleu]);
int toAdd = 1e18;
if (!iRouge and !iBleu)
toAdd = 0;
if (iRouge and iBleu)
toAdd = min(toAdd, dp[iRouge - 1][iBleu - 1]);
if (iRouge)
toAdd = min(toAdd, dp[iRouge - 1][iBleu]);
if (iBleu)
toAdd = min(toAdd, dp[iRouge][iBleu - 1]);
dp[iRouge][iBleu] += toAdd;
// cout << iRouge << ' ' << iBleu << ' ' << dp[iRouge][iBleu] << endl;
}
return dp[nbRouges - 1][nbBleus - 1];
}
int min_total_length(vector<signed> r, vector<signed> b) {
int nbRouges = r.size();
int nbBleus = b.size();
vector<int> position;
for (int x : r)
position.push_back(x);
for (int x : b)
position.push_back(x);
sort(position.begin(), position.end());
int nbPos = nbBleus + nbRouges;
vector<int> side(nbPos);
for (int i = 0; i < nbPos; ++i) {
auto it = lower_bound(r.begin(), r.end(), position[i]);
if (it == r.end() or *it != position[i])
side[i] = 1;
}
vector<int> closestDifferent(nbPos, -1);
vector<int> dp(nbPos + 1, INF);
dp[0] = 0;
for (int iPos = 1; iPos < nbPos; ++iPos) {
dp[iPos + 1] = INF;
int same = iPos;
while (same > 0 and side[same - 1] == side[iPos])
--same;
if (!same)
continue;
int diff = same - 1;
while (diff > 0 and side[diff - 1] == side[diff])
--diff;
int costDis = 0;
int cntRight = 0;
for (int i = same; i <= iPos; ++i)
costDis += position[i], cntRight++;
int cntLeft = 0;
for (int lstTake = same - 1; lstTake >= diff; --lstTake) {
cntLeft++;
costDis -= position[lstTake];
int cst = costDis;
if (cntRight > cntLeft)
cst -= (cntRight - cntLeft) * position[same - 1];
else if (cntRight < cntLeft)
cst += (cntLeft - cntRight) * position[same];
dp[iPos + 1] = min(dp[iPos + 1], min(dp[lstTake], dp[lstTake + 1]) + cst);
}
}
// for (int x : dp)
// cout << x << ' ';
// cout << endl;
return dp.back();
}
