//#include "grader.cpp"
#include "wiring.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define ll long long
#define OK puts("OK");
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 5e5+10;
const int nn = 2e5;
const ll inf = 2e9+7;
ll n, m, x, b;
ll dp[N], sum[N];
ll pr[N];
vector <pair <ll, ll> > all;
ll get(int l, int r) {
return abs(sum[r] - sum[l - 1]);
}
long long min_total_length(vector<int> R, vector<int> B) {
n = sz(R);
m = sz(B);
for(int i = 0; i < n; i++) {
all.pb(mk(R[i], 1));
dp[i+1] = inf;
}
for(int i = 0; i < m; i++) {
all.pb(mk(B[i], 0));
dp[i + n + 1] = inf;
}
/**
if(R[n - 1] < B[0]) {
ll ans = 0;
for(int i = 0; i < n - 1; i++)
ans += abs(R[n - 1] - R[i]);
for(int i = 1; i < sz(B); i++)
ans += abs(B[i] - B[0]);
return ans + max(n, m) * (B[0] - R[n - 1]);
}
**/
R.insert(R.begin(), -inf);
R.insert(R.end(), inf);
B.insert(B.begin(), -inf);
B.insert(B.end(), inf);
n += m;
all.pb(mk(-inf, -1));
sort(all(all));
memset(pr, -1, sizeof(pr));
pr[nn] = 0;
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + (all[i].sc ? -all[i].fr : all[i].fr);
b += (all[i].sc ? -1 : 1);
int j = pr[b + nn];
pr[b + nn] = i;
ll nl, nr;
if (all[i].sc) {
nl = *(lower_bound(B.begin(), B.end(), all[i].first) - 1);
nr = *lower_bound(B.begin(), B.end(), all[i].first);
}
else {
nl = *(lower_bound(R.begin(), R.end(), all[i].first) - 1);
nr = *lower_bound(R.begin(), R.end(), all[i].first);
}
dp[i] = dp[i - 1] + min(all[i].first - nl, nr - all[i].first);
if(j == -1) continue;
dp[i] = min(dp[i], dp[j] + get(j + 1, i));
}
return dp[n];
}
