#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000000LL
lld xx, yy, n;
vector<pair<lld, lld> > a;
vector<lld> dp;
struct item{ //ALTERAR
lld val;
item(){
val = INF;
}
item(lld valval){
val = valval;
}
};
item merge_neut = item(INF); //ALTERAR
item apply_neut = item(0); //ALTERAR
item merge(item a, item b){ //ALTERAR
return a.val<b.val?a:b;
}
item apply_lazy(item x, item l, lld len){ //ALTERAR
return item(x.val+l.val);
}
item apply_lazy_pure(item x, item l){ //ALTERAR
return item(x.val+l.val);
}
item build_leaf(lld pos){ //ALTERAR
return item(0);
}
struct ST{
vector<item> st;
vector<item> lazy;
void init(){
lld sz = 1;
while(sz<n) sz*=2;
st.resize(2*sz);
lazy.resize(2*sz);
}
void build(lld v = 1, lld tl = 0, lld tr = n-1){
if(tl==tr) {
st[v] = build_leaf(tl);
lazy[v] = apply_neut;
}else{
lld tm = (tl+tr)/2;
build(2*v, tl, tm);
build(2*v+1,tm+1,tr);
st[v] = merge(st[2*v], st[2*v+1]);
lazy[v] = apply_neut;
}
}
void push(int v, int tl, int tr){
st[v] = apply_lazy(st[v], lazy[v], tr-tl+1);
if(tl!=tr){
lazy[2*v] = apply_lazy_pure(lazy[2*v], lazy[v]);
lazy[2*v+1] = apply_lazy_pure(lazy[2*v+1], lazy[v]);
}
lazy[v] = apply_neut;
}
item query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){
push(v, tl, tr);
if(l>r) return merge_neut;
if(l<=tl&&tr<=r){
return st[v];
}
lld tm = (tl+tr)/2;
return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr));
}
void upd(lld l, lld r, item val, lld v=1,lld tl=0, lld tr=n-1){
push(v,tl,tr);
if(l>r) return;
if(l<=tl&&tr<=r){
lazy[v] = apply_lazy_pure(lazy[v], val);
push(v,tl,tr);
return;
}
lld tm = (tl+tr)/2;
upd(l,min(r,tm), val, 2*v, tl, tm);
upd(max(l,tm+1),r, val, 2*v+1, tm+1, tr);
st[v] = merge(st[2*v], st[2*v+1]);
}
};
ST seg;
lld min_total_length(vector<int> r, vector<int> b){
xx = (lld) r.size(); yy = (lld) b.size();
n = xx+yy;
for(lld i=0;i<xx;i++) a.push_back({r[i], 1});
for(lld i=0;i<yy;i++) a.push_back({b[i], -1});
sort(a.begin(), a.end());
a.push_back({INF, 0});
dp.resize(n+1); dp[n]=0;
lld block = 0;
lld nxt_beg = n, nxt_end = n, this_end = n;
seg.init(); seg.build();
for(lld i=n-1;i>=0;i--){
if(a[i].second!=a[i+1].second){
block++;
nxt_beg = i+1;
nxt_end = this_end;
this_end = i;
if(block==1){
dp[i] = INF;
continue;
}
lld sum_ai = 0;
for(lld j=nxt_beg;j<=nxt_end;j++){
sum_ai += a[j].first;
seg.upd(j, j, sum_ai-(j+1-nxt_beg)*a[i].first+dp[j+1]);
}
}else{
if(block==1){
dp[i] = INF;
continue;
}
lld pos_block = nxt_beg-i-1;
seg.upd(nxt_beg, nxt_beg+pos_block-1, a[nxt_beg].first-a[i].first);
seg.upd(nxt_beg+pos_block, nxt_end, a[nxt_beg-1].first-a[i].first);
}
dp[i] = seg.query(nxt_beg, nxt_end).val;
}
return dp[0];
}
