#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
const long long N = 1e5 + 5, INF = 2e18;
struct SegTree{
long long tree[N * 4], lazy[N * 4];
void push(int v){
if(lazy[v]){
tree[v] += lazy[v];
if(v * 2 < N * 4) lazy[v * 2] += lazy[v], tree[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
}
long long merge(long long a, long long b){
return min(a, b);
}
void build(int v, int l, int r, vector<long long> &arr){
lazy[v] = tree[v] = 0;
if(l == r) tree[v] = arr[l];
else{
int m = l + (r - l) / 2;
build(v * 2, l, m, arr);
build(v * 2 + 1, m + 1, r, arr);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
}
void update(int v, int tl, int tr, int l, int r, long long val){
if(l > r) return;
else if(tl == l && tr == r) lazy[v] += val;
else{
push(v);
int tm = tl + (tr - tl) / 2;
update(v * 2, tl, tm, l, min(tm, r), val);
update(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, val);
push(v * 2), push(v * 2 + 1);
tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
}
}
long long query(){
push(1);
return tree[1];
}
};
SegTree sgt;
struct Item{
vector<int> pos;
vector<long long> prefix, suffix, dp;
};
long long min_total_length(vector<int> r, vector<int> b){
vector<pair<int, bool>> v;
for(auto x : r) v.push_back({x, false});
for(auto x : b) v.push_back({x, true});
sort(v.begin(), v.end());
vector<Item> vec;
vec.push_back({{v.front().first}, {}, {}, {}});
for(int i = 1; i < v.size(); i++){
if(v[i].second == v[i - 1].second) vec.back().pos.push_back(v[i].first);
else vec.push_back({{v[i].first}, {}, {}, {}});
}
for(auto &itm : vec){
itm.prefix.assign(itm.pos.size(), 0);
itm.suffix.assign(itm.pos.size(), 0);
itm.dp.assign(itm.pos.size() + 1, 0);
for(int i = 1; i < itm.pos.size(); i++) itm.prefix[i] = itm.prefix[i - 1] + (itm.pos[i] - itm.pos.front());
for(int i = (int)itm.pos.size() - 2; i >= 0; i--) itm.suffix[i] = itm.suffix[i + 1] + (itm.pos.back() - itm.pos[i]);
}
for(int i = 1; i < vec[0].dp.size(); i++) vec[0].dp[i] = INF;
for(int cur = 1; cur < vec.size(); cur++){
vector<long long> prvdp = vec[cur - 1].dp;
for(int i = 0; i < vec[cur - 1].pos.size(); i++) prvdp[i] += vec[cur - 1].suffix[i] + 1ll * (vec[cur - 1].pos.size() - i) * (vec[cur].pos.front() - vec[cur - 1].pos.back());
sgt.build(1, 0, prvdp.size() - 1, prvdp);
vec[cur].dp[0] = sgt.query();
for(int i = 1; i < vec[cur].dp.size(); i++){
sgt.update(1, 0, prvdp.size() - 1, max((int)prvdp.size() - i, 0), prvdp.size() - 1, vec[cur].pos.front() - vec[cur - 1].pos.back());
vec[cur].dp[i] = sgt.query() + vec[cur].prefix[i - 1];
}
}
return vec.back().dp.back();
}
