#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 2e5 + 10, off = (1 << 18);
const ll inf = (1LL << 60);
ll tour[2][2 * off];
ll prop[2][2 * off];
ll dp[maxn];
vector <pair<int, int> > v;
vector <int> poc;
void push(bool f, int x){
if(x >= off) return;
ll val = prop[f][x];
prop[f][x] = 0;
tour[f][x * 2] += val;
prop[f][x * 2] += val;
tour[f][x * 2 + 1] += val;
prop[f][x * 2 + 1] += val;
}
void update(bool f, int x, int lo, int hi, int l, int r, ll val){
if(r <= l) return;
push(f, x);
if(hi <= l || r <= lo) return;
if(l <= lo && hi <= r){
tour[f][x] += val;
prop[f][x] += val;
return;
}
int mid = (lo + hi) / 2;
update(f, x * 2, lo, mid, l, r, val);
update(f, x * 2 + 1, mid, hi, l, r, val);
tour[f][x] = min(tour[f][x * 2], tour[f][x * 2 + 1]);
}
ll query(bool f, int x, int lo, int hi, int l, int r){
if(r <= l) return inf;
push(f, x);
if(hi <= l || r <= lo) return inf;
if(l <= lo && hi <= r){
return tour[f][x];
}
int mid = (lo + hi) / 2;
return min(query(f, x * 2, lo, mid, l, r), query(f, x * 2 + 1, mid, hi, l, r));
}
ll min_total_length(vector<int> r, vector<int> b) {
for(int i = 0; i < r.size(); i++){
v.push_back({r[i], 0});
}
for(int i = 0; i < b.size(); i++){
v.push_back({b[i], 1});
}
sort(v.begin(), v.end());
poc.push_back(0);
for(int i = 0; i < v.size(); i++){
// cout << v[i].fi << ' ' << v[i].se << endl;
if(!i || v[i].se != v[i - 1].se){
// cout << "sad " << i << endl;
poc.push_back(i);
}
}
// cout << poc.size() << endl;
poc.push_back(v.size());
// for(int i = 0; i < poc.size(); i++){
// cout << poc[i] << ' ';
// }
// cout << endl;
int p = 0;
for(int i = 0; i < v.size(); i++){
int x = v[i].fi;
int c = v[i].se;
// cout << "x c: " << x << ' ' << c << endl;
while(poc[p + 1] <= i) p++;
int l = poc[p - 1], r = poc[p], nxt = poc[p + 1];
// cout << "l r nxt: " << l << ' ' << r << ' ' << nxt << endl;
// if(i == r) update(0, 1, 0, off, l)
if(r - (i - r) > l){
update(c, 1, 0, off, l, r - (i - r), x - v[r].fi);
// cout << "update1 " << c << ' ' << l << ' ' << r - (i - r) << ' ' << x - v[r].fi << endl;
}
if(r){
update(c, 1, 0, off, r - (i - r), r, x - v[r - 1].fi);
// cout << "update2 " << c << ' ' << r - (i - r) << ' ' << r << ' ' << x - v[r - 1].fi << endl;
}
dp[i] = query(c, 1, 0, off, l, r);
// cout << "dp: " << i << ' ' << dp[i] << endl;
if(nxt != i + 1) update(!c, 1, 0, off, i + 1, i + 2, dp[i]);
else{
if(r == i){
ll q = query(!c, 1, 0, off, i, i + 1);
// if(i == 0) cout << q << ' ' << dp[i] << endl;
if(dp[i] < q) update(!c, 1, 0, off, i, i + 1, dp[i] - q);
}
update(c, 1, 0, off, i + 1, i + 2, dp[i]);
// cout << "update3 " << c << ' ' << i + 1 << ' ' << i + 2 << ' ' << dp[i] << endl;
}
update(!c, 1, 0, off, r, i + 1, v[nxt].fi - x);
// cout << "update4 " << c << ' ' << r << ' ' << i + 1 << ' ' << v[nxt].fi - x << endl;
}
ll ans = dp[v.size() - 1];
return ans;
}
