// ~ Be Name Khoda ~ //
#include "wiring.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
ll dp[2][maxn5], pre[maxn5], suf[maxn5], cost[maxn5];
vector <pair<ll, int>> av;
void build(int ty, int n, ll dis){
pre[0] = dp[ty][0];
for(int i = 1; i <= n; i++)
pre[i] = min(pre[i - 1], dp[ty][i] - dis * i);
suf[n] = dp[ty][n];
for(int i = n - 1; i >= 0; i--)
suf[i] = min(suf[i + 1], dp[ty][i]);
/*
cout << "in " << ty << ' ' << n << ' ' << dis << endl;
for(int i = 0; i <= n; i++)
cout << i << ' ' << pre[i] << ' ' << suf[i] << ' ' << dp[ty][i] << endl;
*/
}
ll get_min(int x, int n, ll dis){
ll ans = pre[min(x, n)];
if(n >= x)
ans = min(ans, suf[x] - dis * x);
//cout << "getting min of " << x << ' ' << n << ' ' << dis << ' ' << ans << endl;
return ans;
}
long long min_total_length(std::vector<int> r, std::vector<int> b){
for(int i = 0; i < r.size(); i++)
av.pb({r[i], 0});
for(int i = 0; i < b.size(); i++)
av.pb({b[i], 1});
sort(all(av));
int last = 0, n = 0;
for(int i = 0; i < av.size(); i++){
if(av[i].se == av[last].se)
continue;
//cout << "ok " << i << ' ' << last << ' ' << n << endl;
if(n == 0){
n = i - last;
for(int j = 0; j < n; j++)
dp[av[last].se][j] = inf;
for(int j = last; j < i; j++)
dp[av[last].se][n] += av[i].fi - av[j].fi;
build(av[last].se, n, av[i].fi - av[i - 1].fi);
last = i;
continue;
}
int m = i - last;
ll cur = 0;
fill(cost, cost + m + 4, 0);
for(int j = last; j <= i; j++){
cost[m - (j - last)] = cur;
cur += av[j].fi - av[last - 1].fi;
}
//cout << cost[0] << endl;
for(int j = 0; j < m; j++)
dp[av[last].se][j] = get_min(m - j, n, av[last].fi - av[last - 1].fi) + cost[j];
dp[av[last].se][m] = dp[av[last].se ^ 1][0] + cost[m];
cur = 0;
for(int j = i - 1; j >= last; j--){
cur += av[i].fi - av[j].fi;
dp[av[last].se][m - (j - last)] += cur;
}
build(av[last].se, m, av[i].fi - av[i - 1].fi);
n = m;
last = i;
}
int i = av.size();
int m = i - last;
ll cur = 0;
for(int j = last; j <= i; j++){
cost[m - (j - last)] = cur;
if(j < i)
cur += av[j].fi - av[last - 1].fi;
}
for(int j = 0; j < 1; j++)
dp[av[last].se][j] = get_min(m - j, n, av[last].fi - av[last - 1].fi) + cost[j];
return dp[av[last].se][0];
}
