#include "wiring.h"
#include <vector>
#include <algorithm>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 2e5;
int const coordmax = 1e9;
ll const inf = 1LL * coordmax * coordmax;
struct Wire{
int color;
int dist;
bool operator < (Wire const &a) const{
return dist < a.dist;
}
};
std::vector<Wire> v;
ll dp[1 + nmax], sum[1 + nmax];
std::vector<int> changes;
ll getsum(int x, int y){
if(x == 0)
return sum[y];
else
return sum[y] - sum[x - 1];
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size() + b.size();
v.push_back({0, -1}); ///just for filling the empty space
for(int i = 0; i < r.size(); i++)
v.push_back({1, r[i]});
for(int i = 0; i < b.size(); i++)
v.push_back({2, b[i]});
v.push_back({0, coordmax + 1});
std::sort(v.begin(), v.end());
for(int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + v[i].dist;
for(int i = 1; i <= n; i++)
if(v[i - 1].color != v[i].color)
changes.push_back(i);
changes.push_back(n + 1);
for(int i = 1; i <= n; i++)
dp[i] = inf;
dp[0] = 0;
for(int group = 1; group < changes.size() - 1; group++){
int x = changes[group], y = changes[group + 1] - 1, lim = changes[group - 1];
ll result = inf;
for(int i = y; x <= i; i--){
if(i < y)
result = result - v[i + 1].dist + v[x].dist;
int x2 = x - 1 - (i - x);
if(lim <= x2) {
result = MIN(result, MIN(dp[x2], dp[x2 - 1]) + getsum(x, i) - getsum(x2, x - 1));
ll adaos = 0;
while(i == y && lim <= x2){
result = MIN(result, MIN(dp[x2], dp[x2 - 1]) + getsum(x, i) - getsum(x2, x - 1) + adaos);
x2--;
adaos += v[x].dist;
}
}
dp[i] = MIN(dp[i], result);
}
result = inf;
for(int i = x; i <= y; i++){
result = result + v[i].dist - v[x - 1].dist;
int x2 = x - 1 - (i - x);
if(lim <= x2)
result = MIN(result, MIN(dp[x2], dp[x2 - 1]) + getsum(x, i) - getsum(x2, x - 1));
dp[i] = MIN(dp[i], result);
}
/*
std::cout << group << " " << x << " " << y << '\n';
for(int i = x; i <= y; i++)
std::cout << dp[i] << " ";
std::cout << '\n' << '\n';
//*/
}
return dp[n];
}
