#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "wiring.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using i32 = int32_t;
using pii = pair<int, int>;
// int solve_13(const vector<i32> &v1, const vector<i32> &v2) {
// int sl = 0, sr = 0;
// for(auto &i:v1) sl += i;
// sl += max(0ll, sz(v2) - sz(v1)) * v1.back();
// for(auto &i:v2) sr += i;
// sr += max(0ll, sz(v1) - sz(v2)) * v2.front();
// return sr - sl;
// }
// int cost(const vector<pii> &v, int l, int r) {
// vector<i32> vl, vr;
// For(i, l, r) {
// if(v[i].S == v[l].S) vl.eb(v[i].F);
// else vr.eb(v[i].F);
// }
// return solve_13(vl, vr);
// }
const int MAXN = 100'000;
const int MAXND = MAXN * 4;
const int INF = 4e18;
#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
int add[MAXND + 10];
int mn[MAXND + 10];
void pull(int id) {
mn[id] = min(mn[L(id)], mn[R(id)]) + add[id];
}
void build(int id, int l, int r) {
add[id] = 0;
mn[id] = INF;
if(l == r) return;
int m = (l + r) / 2;
build(L(id), l, m);
build(R(id), m + 1, r);
}
void single_upd(int id, int l, int r, int pos, int val) {
if(l == r) {
mn[id] = val;
return;
}
int m = (l + r) / 2;
if(pos <= m) single_upd(L(id), l, m, pos, val);
else single_upd(R(id), m + 1, r, pos, val);
pull(id);
}
void range_add(int id, int l, int r, int L, int R, int val) {
if(l >= L && r <= R) {
add[id] += val;
mn[id] += val;
return;
}
int m = (l + r) / 2;
if(L <= m) range_add(L(id), l, m, L, R, val);
if(R > m) range_add(R(id), m + 1, r, L, R, val);
pull(id);
}
int qry() {
return mn[0];
}
void out(int id, int l, int r, int tot) {
if(l == r) {
cerr << " " << (tot + mn[id]);
return;
}
tot += add[id];
int m = (l + r) / 2;
out(L(id), l, m, tot);
out(R(id), m + 1, r, tot);
}
} seg;
int dp[MAXN + 10];
int min_total_length(vector<int32_t> r, vector<int32_t> b) {
int n = sz(r), m = sz(b);
assert(max(n, m) <= MAXN);
vector<pii> v; // pos, color
v.eb(-1, -1);
for(auto &i:r) v.eb(i, 0);
for(auto &i:b) v.eb(i, 1);
sort(all(v));
dp[0] = 0;
int l1, r1, l2;
int r2 = 1;
while(v[r2].S == v[1].S) {
dp[r2] = INF;
r2++;
}
l1 = r1 = 0; l2 = 1;
for(; r2 <= n + m; r2++) {
if(v[r2].S != v[r2 - 1].S) {
l1 = l2; r1 = r2 - 1; l2 = r2;
seg.build(0, l1, r1);
int tot = 0;
Forr(i, r1, l1) {
tot += v[r2].F - v[i].F;
seg.single_upd(0, l1, r1, i, min(dp[i], dp[i - 1]) + tot);
}
} else {
int p = r1 - (r2 - l2);
if(p > l1) {
seg.range_add(0, l1, r1, l1, p - 1, v[r2].F - v[r1].F);
seg.range_add(0, l1, r1, p, r1, v[r2].F - v[l2].F);
} else {
seg.range_add(0, l1, r1, l1, r1, v[r2].F - v[r1].F);
}
}
dp[r2] = seg.qry();
// cerr << r2 << " " << dp[r2] << "\n";
// cerr << r2 << ":";
// seg.out(0, l1, r1, 0);
// cerr << "\n";
// For(j, l1, r1) {
// dp[r2] = min({dp[r2], dp[j - 1] + cost(v, j, r2), dp[j] + cost(v, j, r2)});
// }
// cerr << l1 << " " << r1 << " " << l2 << " " << r2 << "\n";
}
return dp[n + m];
}
/*
4 5
1 2 3 7
0 4 5 9 10
10
*/
