#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18 + 123;
int n, m;
ll min_total_length(vector<int> r, vector<int> b) {
n = r.size();
m = b.size();
vector<pair<int,int>>all;
for (int i : r) all.emplace_back(i, 0);
for (int i : b) all.emplace_back(i, 1);
sort(all.begin(), all.end());
vector<vector<ll>>gr;
for (int i = 0 ; i < n + m ; ) {
int j = i;
while (j < n + m && all[i].second == all[j].second) ++j;
gr.emplace_back();
for (; i < j ; ++ i) {
gr.back().emplace_back(all[i].first);
//cerr << all[i].first << " ";
}
//cerr << "=======\n";
}
int sz = gr.size();
vector<vector<ll>>dp(sz);
vector<int>g(sz);
vector<vector<ll>>p(sz), s(sz);
for (int i = 0 ; i < sz ; ++ i) {
dp[i].assign((int)gr[i].size() + 1, inf);
g[i] = gr[i].size();
p[i].assign((int)gr[i].size() + 1, 0);
for (int j = 1 ; j <= g[i] ; ++ j) {
p[i][j] = p[i][j - 1] + gr[i][j - 1];
}
s[i].assign((int)gr[i].size() + 1, 0);
for (int j = 1 ; j <= g[i] ; ++ j) {
s[i][j] = s[i][j - 1] + gr[i][g[i] - j];
}
}
dp[0][g[0]] = 0;
for (int i = 0 ; i < sz ; ++ i) {
for (int j = g[i] ; j > 0 ; -- j) {
if (i + 1 < sz && j <= g[i + 1]) {
dp[i + 1][g[i + 1] - j] = min(dp[i + 1][g[i + 1] - j], dp[i][j] + p[i + 1][j] - s[i][j]);
}
if (i + 1 < sz) {
dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + gr[i + 1][0] - gr[i][g[i]-j]);
}
if (i > 0) {
dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + gr[i][g[i]-j] - gr[i - 1][g[i - 1]-1]);
}
}
if (i + 1 < sz) dp[i + 1][g[i + 1]] = min(dp[i + 1][g[i + 1]], dp[i][0]);
}
return dp[sz-1][0];
}
