#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
static const ll INF = 1e18;
struct Node {
ll mn;
Node(ll _mn = INF) : mn(_mn) { }
};
class SegTree {
public:
vector <Node> aint;
int n;
inline void init(int _n) {
n = _n;
aint.resize(4 * n + 5);
}
inline void update(int l, int r, Node cur) { // l == r ???
update(1, 0, n, l, r, cur);
}
inline Node query(int l, int r) {
return query(1, 0, n, l, r);
}
private:
inline Node combine(Node a, Node b) {
return Node(min(a.mn, b.mn));
}
void update(int nod, int left, int right, int l, int r, Node cur) {
if(l <= left && right <= r) {
aint[nod] = combine(aint[nod], cur);
return ;
}
int mid = (left + right) / 2;
if(l <= mid) update(2 * nod, left, mid, l, r, cur);
if(mid < r) update(2 * nod + 1, mid + 1, right, l, r, cur);
aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
}
Node query(int nod, int left, int right, int l, int r) {
if(l <= left && right <= r) {
return aint[nod];
}
int mid = (left + right) / 2;
Node ans(INF);
if(l <= mid) ans = combine(ans, query(2 * nod, left, mid, l, r));
if(mid < r) ans = combine(ans, query(2 * nod + 1, mid + 1, right, l, r));
return ans;
}
};
ll min_total_length(vector<int> r, vector<int> b) {
vector < pair <int, int> > x(1);
for(auto it : r) {
x.push_back({it, 0});
}
for(auto it : b) {
x.push_back({it, 1});
}
sort(x.begin(), x.end());
int i, n = r.size() + b.size();
vector <int> last(n + 1, 0), nxt(n + 2, n + 1);
vector <ll> sp(n + 1);
for(i = 1; i <= n; i++) {
last[i] = ((x[i].second ^ x[i - 1].second) ? i - 1 : last[i - 1]);
sp[i] = sp[i - 1] + x[i].first;
//cerr << x[i].first << " ";
}
for(i = n; i >= 1; i--) {
nxt[i] = ((x[i].second ^ x[i + 1].second) ? i + 1 : nxt[i + 1]);
}
SegTree st1, st2; st1.init(n), st2.init(n);
vector <ll> dp(n + 1);
for(i = 1; i <= n; i++) {
st1.update(i - 1, i - 1, Node(dp[i - 1] - 1LL * (i - 1) * x[nxt[i] - 1].first + sp[i - 1]));
st2.update(i - 1, i - 1, Node(dp[i - 1] - 1LL * (i - 1) * x[nxt[i] - 1].first + sp[i - 1]
+ 1LL * (nxt[i] - i) * (x[nxt[i]].first - x[nxt[i] - 1].first)));
if(last[i] == 0) { dp[i] = INF; continue; }
int a = last[i] - last[last[i]], b = i - last[i];
ll cur = sp[i] - sp[last[i]] - 1LL * (i - last[i]) * x[last[i] + 1].first - sp[last[i]] + 1LL * x[last[i]].first * last[i];
dp[i] = cur + 1LL * (i - last[i]) * (x[last[i] + 1].first - x[last[i]].first) + st1.query(max(0, last[i] - b), last[i] - 1).mn;
if(a > b) {
dp[i] = min(dp[i], cur + st2.query(last[last[i]], last[i] - b).mn);
}
if(a == 1) {
dp[i] = min(dp[last[i]] + sp[i] - sp[last[i]] - 1LL * x[last[i]].first * b, dp[i]);
}
}
return dp[n];
}
