#include "wiring.h"
#include <bits/stdc++.h>
namespace {
using namespace std;
const long long INF = 1e18;
struct dat {
int x, color;
};
int N;
vector<dat> points;
vector<long long> dp;
vector<int> lpos[2];
long long solve() {
lpos[0].resize(N);
lpos[1].resize(N);
for(int i = 0; i < N; i++) {
int c = points[i].color;
lpos[c][i] = i;
if(i == 0) lpos[!c][i] = -1;
else lpos[!c][i] = lpos[!c][i-1];
}
dp.resize(N + 1);
dp[N] = 0;
vector<int> C(N);
for(int i = N-1; i >= 0; i--) {
int j = i; long long as = 0; long long ac = 0;
dp[i] = INF;
long long las = 0;
while(j < N && points[j].color == points[i].color) {
as += points[j].x; ac++;
if(int pi = lpos[!points[j].color][i]; pi != -1) {
long long cst = as - ac * points[pi].x;
if(cst+dp[j+1] < dp[i]) {
dp[i] = cst + dp[j+1];
C[i] = j;
}
}
las = points[j].x;
j++;
}
if(j == N) {
//fprintf(stderr, "broke dp[%d] = %lld\n", points[i].x, dp[i]);
continue;
}
long long bs = 0, bc = 0;
long long fbs = points[j].x;
for(; j < N; j++) {
bs += points[j].x; bc++;
long long as_cp = as, bs_cp = bs;
if(ac > bc) bs_cp += fbs * (ac - bc);
else if(ac < bc) as_cp += las * (bc - ac);
long long cost = bs_cp - as_cp;
if(cost + dp[j+1] < dp[i]) {
dp[i] = cost + dp[j+1];
C[i] = j;
}
}
//std::fprintf(stderr, "dp[%d] = %lld\n", points[i].x, dp[i]);
}
return dp[0];
}
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
N = r.size() + b.size();
int i = 0, j = 0;
points.resize(N);
int R = r.size(), B = b.size();
while(i < R && j < B) {
if(r[i] < b[j]) {
points[i + j] = dat{r[i], 0};
i++;
} else {
points[i + j] = dat{b[j], 1};
j++;
}
}
while(i < R) {
points[i + j] = dat{r[i], 0};
i++;
}
while(j < B) {
points[i + j] = dat{b[j], 1};
j++;
}
return solve();
}
