#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"
int n;
const long long inf = 1e18;
vector<int> groupInd;
vector<pair<int, int> > interv;
vector<pair<int, int> > groups;
long long f(int l, int r) {
int prm = groups[l].second;
int ant = groups[r].second;
long long kekL = 0, kekR = 0;
long long maxL = 0, minR = 1e9;
long long sumL = 0, sumR = 0;
for(int i = l; i <= r; i++) {
kekL += (groups[i].second == prm);
kekR += (groups[i].second == ant);
if(groups[i].second == prm) {
sumL += groups[i].first;
maxL = max(maxL, 1ll * groups[i].first);
}else {
sumR += groups[i].first;
minR = min(minR, 1ll * groups[i].first);
}
}
long long ret = 0;
ret += kekL * maxL - sumL;
ret += sumR - kekR * minR;
ret += (minR - maxL) * max(kekL, kekR);
return ret;
}
long long min_total_length(vector<int> r, vector<int> b) {
n = r.size() + b.size();
for(auto &x : r) {
groups.push_back({x, 0});
}
for(auto &x : b) {
groups.push_back({x, 1});
}
groupInd.resize(n);
sort(groups.begin(), groups.end());
for(int i = 0; i < n; i++) {
for(int j = i; j <= n; j++) {
if(j == n || groups[j].second != groups[i].second) {
int l = i;
int r = j-1;
interv.push_back({l, r});
for(int h = l; h <= r; h++) {
groupInd[h] = (int) interv.size()-1;
}
i = j-1;
break;
}
}
} /*
cout << "intervalai: ";
for(auto &x : interv) {
cout << "(" << x.first << ", " << x.second << "), ";
}
cout << endl;*/
vector<long long> dp(n, inf);
// dp[-1] = 0;
for(int i = interv[1].first; i < n; i++) {
int myInterv = groupInd[i];
// cout << "skaiciuoju dp[" << i << "], manoInterv = " << myInterv << ":" << endl;
dp[i] = dp[interv[myInterv-1].second] + f(interv[myInterv-1].second, i);
for(int j = interv[myInterv-1].first; j <= interv[myInterv-1].second; j++) {
dp[i] = min(dp[i], (j == 0 ? 0ll : dp[j-1]) + f(j, i));
// cout << "gali buti (nuo " << j << ") " << (j == 0 ? 0ll : dp[j-1]) << " + f(" << j << ", " << i << ") = " << f(j, i) << endl;
}
// cout << "dp[" << i << "] = " << dp[i] << endl << endl;
}
return dp[n-1];
}
