#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) ((int)(x).size())
const ll INF = 1e18;
int cap;
vector<ll> seg, lazy;
void init(int n){
for(cap=1; cap < n; cap*=2);
seg.assign(2*cap, INF);
lazy.assign(2*cap, 0);
}
void push(int i){
seg[2*i] += lazy[i];
lazy[2*i] += lazy[i];
seg[2*i+1] += lazy[i];
lazy[2*i+1] += lazy[i];
lazy[i] = 0;
}
void add(int l, int r, ll v, int a, int b, int i){
if(l <= a && b <= r){
seg[i] += v;
lazy[i] += v;
}
else if(b < l || r < a) return;
else{
push(i);
int m = (a+b)/2;
add(l, r, v, a, m, 2*i);
add(l, r, v, m+1, b, 2*i+1);
seg[i] = min(seg[2*i], seg[2*i+1]);
}
}
void upd(int p, ll v, int a, int b, int i){
if(a == b) seg[i] = v;
else{
push(i);
int m = (a+b)/2;
if(p <= m) upd(p, v, a, m, 2*i);
else upd(p, v, m+1, b, 2*i+1);
}
}
ll qry(int l, int r, int a, int b, int i){
if(l <= a && b <= r) return seg[i];
if(b < l || r < a) return INF;
push(i);
int m = (a+b)/2;
return min(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
}
struct Block{
int col, cnt, first, last;
Block(int _col, int _cnt, int _first, int _last): col(_col), cnt(_cnt), first(_first), last(_last){}
};
ll min_total_length(vector<int> r, vector<int> b) {
int n = int(r.size()), m = int(b.size());
vector<pair<int, int>> a;
for(int i : r) a.emplace_back(i, 0);
for(int i : b) a.emplace_back(i, 1);
sort(a.begin(), a.end());
vector<ll> dp(n+m+1, INF);
dp[0] = 0;
init(n+m+1);
upd(1, 0, 1, cap, 1);
vector<Block> blocks;
bool three = false;
blocks.emplace_back(a[0].second, 1, 0, 0);
for(int i = 0; i < n+m; i++){
if(blocks.back().col == a[i].second){
if(blocks.size() != 1){
if(three){
dp[i+1] = dp[i] + a[i].first-a[blocks[sz(blocks)-2].last].first;
}
else{
ll small = a[i].first-a[blocks[sz(blocks)-1].first].first;
ll big = a[i].first-a[blocks[sz(blocks)-2].last].first;
int j = blocks[sz(blocks)-2].last - blocks[sz(blocks)-1].cnt;
Block bl = blocks[sz(blocks)-2];
j = max(j, bl.first-1);
add(j+2, bl.last+1, big, 1, cap, 1);
add(bl.first+1, j+1, small, 1, cap, 1);
dp[i+1] = qry(bl.first+1, bl.last+1, 1, cap, 1);
}
}
blocks.back().cnt++;
blocks.back().last = i;
}
else{
three = (int)blocks.size() > 1 && blocks.back().cnt == 1;
if(three){
dp[i+1] = min(dp[i], dp[i-1]) + a[i].first-a[blocks[sz(blocks)-1].last].first;
}
else{
ll cost = 0;
for(int j = blocks.back().last; j >= blocks.back().first; j--){
cost += a[i].first-a[j].first;
add(j+1, j+1, cost, 1, cap, 1);
}
dp[i+1] = qry(blocks.back().first+1, blocks.back().last+1, 1, cap, 1);
}
blocks.emplace_back(a[i].second, 1, i, i);
}
if(dp[i+1] >= INF) continue;
upd(i+2, dp[i+1], 1, cap, 1);
}
return dp[n+m];
}
