#include "wiring.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <random>
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short int
#define pii pair<ll, ll>
#define NEK 1000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
using namespace std;
ll min_total_length(vec<int> r2, vec<int> b2) {
vec<ll> r, b;
vec<pii> p;
For(i, r2.size()) r.push_back(r2[i]);
For(i, b2.size()) b.push_back(b2[i]);
ll pr = r.size();
ll p_b = b.size();
ll n = pr + p_b;
For(i, pr) {
p.push_back({ r[i], 0 });
}
For(i, p_b) {
p.push_back({ b[i], 1 });
}
sort(p.begin(), p.end());
vec<ll> dp(n + 1, NEK);
dp[0] = 0;
vec<ll> bl(n, NEK);
ll pos0 = -1, pos1 = -1;
For(i, n) {
if (p[i].ss == 0) {
pos0 = p[i].ff;
if (pos1 == -1) continue;
bl[i] = min(bl[i], p[i].ff - pos1);
}
if (p[i].ss == 1) {
pos1 = p[i].ff;
if (pos0 == -1) continue;
bl[i] = min(bl[i], p[i].ff - pos0);
}
}
pos0 = -1, pos1 = -1;
rfor(i, n-1) {
if (p[i].ss == 0) {
pos0 = p[i].ff;
if (pos1 == -1) continue;
bl[i] = min(bl[i], pos1 - p[i].ff);
}
if (p[i].ss == 1) {
pos1 = p[i].ff;
if (pos0 == -1) continue;
bl[i] = min(bl[i], pos0 - p[i].ff);
}
}
ll prvy = 0;
ll posl = 0;
ll pointer = -1;
vec<ll> p_vzd(n, -1);
ll trz_vzd = 0;
priority_queue<pii> q;
ll min_pred = NEK;
ffor(i, 1, n + 1) {
//jednoducho ho napoj na najblizsieho
dp[i] = min(dp[i], dp[i - 1] + bl[i - 1]);
if (p[i - 1].ss != p[prvy].ss) {
while (!q.empty()) q.pop();
ll vzd = 0;
for (ll j = i - 2; j >= prvy; j--) {
vzd += p[i - 2].ff - p[j].ff;
p_vzd[j] = vzd;
q.push({ (dp[j] + vzd + (i - 1 - j) * (p[i - 1].ff - p[i - 2].ff)) * (-1), j});
}
posl = prvy;
pointer = i - 2;
prvy = i - 1;
trz_vzd = 0;
min_pred = NEK;
}
trz_vzd += p[i-1].ff - p[prvy].ff;
//vzd1 jedna co si budem predpocitavat
//trz_vzd + vzd2 + dp[i-1] + MAX(POCA, POCB) * (dist)
ll pocb = (i - prvy);
while (pointer >= posl && (prvy - pointer) <= (i - prvy)) {
min_pred = min(min_pred, p_vzd[pointer] + dp[pointer]);
pointer--;
}
//musime vyhodit vsetkych mojov ktory uz zrazu niesu v ponuke
while (!q.empty()) {
if (q.top().ss > pointer) q.pop();
else break;
}
ll min_druhe = NEK;
if (!q.empty()) {
min_druhe = q.top().ff * (-1) + trz_vzd;
}
ll odp = NEK;
if (prvy != 0) {
odp = min_pred + trz_vzd + pocb * (p[prvy].ff - p[prvy - 1].ff);
}
dp[i] = min(dp[i], min(min_druhe, odp));
}
return dp[n];
}
/*
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m; cin >> n >> m;
vec<int> a(n), b(m);
For(i, n) cin >> a[i];
For(i, m) cin >> b[i];
cout << min_total_length(a, b) << '\n';
return 0;
}*/
