#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
#define inf 1000'000'000'000'000'000LL
template<typename T>
using vec = vector<T>;
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
long long min_total_length(std::vector<i32> r, std::vector<i32> b) {
vec<pair<int, int>> points;
vec<vec<int>> cords(2, vec<int>());
for (int i: r) {
points.emplace_back(i, 0);
cords[0].emplace_back(i);
}
for (int i: b) {
points.emplace_back(i, 1);
cords[1].emplace_back(i);
}
sort(cords[0].begin(), cords[0].end());
sort(cords[1].begin(), cords[1].end());
sort(points.begin(), points.end());
int n = points.size();
vec<vec<int>> groups;
for (int i = 0; i < n; i++) {
if (i == 0 || points[i].second != points[i - 1].second) {
groups.emplace_back();
}
groups.back().emplace_back(points[i].first);
}
int m = groups.size();
vec<vec<int>> dp(m);
vec<pair<int, int>> prev;
prev = {{0, groups[0].size()}};
for (int t: groups[0]) {
prev[0].first += groups[0].back() - t;
}
prev.emplace_back(inf, inf);
for (int i = 1; i < m; i++) {
dp[i].resize(groups[i].size() + 1, inf);
int d = groups[i].front() - groups[i - 1].back();
int T = 0;
{
chmin(dp[i][0], prev.back().first);
}
for (int j = 1; j < dp[i].size(); j++) {
T += groups[i][j - 1] - groups[i][0];
dp[i][j] = inf;
for (int k = 0; k < prev.size() - 1; k++) {
int cost = prev[k].first + T + d * (max(j, (int) prev[k].second));
chmin(dp[i][j], cost);
}
}
vec<pair<int, int>> new_prev;
new_prev.emplace_back(dp[i].back(), 0);
int P = 0;
for (int j = dp[i].size() - 2; j >= 0; j--) {
P += groups[i].back() - groups[i][j];
new_prev.emplace_back(dp[i][j] + P, dp[i].size() - j - 1);
}
reverse(new_prev.begin(), new_prev.end());
prev = new_prev;
}
return dp[m - 1].back();
}
