#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define st first
#define nd second
using namespace std;
const ll INF = 1e15+1;
ll min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
vector<pair<int, bool>> p;
for(int i: r) {
p.push_back({i, 0});
}
for(int i: b) {
p.push_back({i, 1});
}
sort(p.begin(), p.end());
vector<vector<ll>> block;
for(int i=0; i<n+m; ++i) {
if(i==0 || p[i].nd!=p[i-1].nd) {
block.push_back({});
}
block.back().push_back(p[i].st);
}
vector<vector<ll>> dp(2, vector<ll> (max(n,m)+1));
for(int i=1; i<=(int)block[0].size(); ++i) {
dp[0][i]=INF;
}
auto prev=block[0];
block.erase(block.begin());
bool type = 1;
int nr=0;
for(auto i: block) {
dp[type][0] = dp[!type][(int)prev.size()];
vector<ll> suf(prev.size()+1);
for(int j=1; j<=(int)prev.size(); ++j) {
suf[j] = suf[j-1]+prev[(int)prev.size()-j];
}
ll pref=0;
int k = 0;
if(nr==0) k=(int)prev.size();
for(int j=1; j<=(int)i.size(); ++j) {
pref+=i[j-1];
while(k<(int)prev.size()) {
ll v1 = pref - suf[k] - max(0LL, (ll)j-k)*prev.back() + max(0LL, (ll)k-j)*i[0] + dp[!type][(int)prev.size()-k];
ll v2 = pref - suf[k+1] - max(0LL, (ll)j-k-1)*prev.back() + max(0LL, (ll)k+1-j)*i[0]+ dp[!type][(int)prev.size()-k-1];
if(v2<=v1) k++;
else break;
}
dp[type][j] = pref - suf[k] - max(0LL, (ll)j-k)*prev.back() + max(0LL, (ll)k-j)*i[0] + dp[!type][(int)prev.size()-k];
}
prev = i;
type ^= 1;
nr++;
}
return dp[!type][(int)prev.size()];
}
