#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const ll INF = 1e18;
int N, M;
ll A[MAXN+10], B[MAXN+10], D[MAXN+10];
ll ans=0;
pll C[MAXN+10];
ll dp[MAXN+10];
int P[MAXN+10], Q[MAXN+10];
ll tree[MAXN*4+10], lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
if(lazy[node]==0) return;
tree[node]+=lazy[node];
if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
lazy[node]=0;
return;
}
void update2(int node, int tl, int tr, int p, ll k)
{
busy(node, tl, tr);
if(tl==tr) { tree[node]=k; return; }
int mid=tl+tr>>1;
if(p<=mid) update2(node*2, tl, mid, p, k);
else update2(node*2+1, mid+1, tr, p, k);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
void update(int node, int tl, int tr, int l, int r, ll k)
{
if(l>r) return;
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
lazy[node]=k;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
ll query(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return INF;
int mid=tl+tr>>1;
return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
ll min_total_length(vector<int> _A, vector<int> _B)
{
N=_A.size(); M=_B.size();
for(int i=1; i<=N; i++) A[i]=_A[i-1];
for(int i=1; i<=M; i++) B[i]=_B[i-1];
for(int i=1; i<=N; i++) C[i]={A[i], 1};
for(int i=1; i<=M; i++) C[i+N]={B[i], 2};
sort(C+1, C+N+M+1);
for(int i=1; i<=N+M; i++) D[i]=D[i-1]+C[i].first;
P[1]=0;
for(int i=2; i<=N+M; i++)
{
if(C[i].second==C[i-1].second) P[i]=P[i-1];
else P[i]=i-1;
}
int bef;
for(int i=N+M; i>=1; i--)
{
if(C[i].second!=C[i+1].second) bef=i;
Q[i]=bef;
}
ll val=0;
for(int i=1; i<=N+M; i++)
{
dp[i]=1e17;
if(P[i]==0)
{
ll t=C[Q[i]].first*(Q[i]-i+1)-(D[Q[i]]-D[i-1])+dp[i-1]+(Q[i]-i)*(C[Q[i]+1].first-C[Q[i]].first);
update2(1, 1, N+M, i, t);
continue;
}
if(C[i].second!=C[i-1].second) val=C[i].first-C[i-1].first;
else val+=C[i].first-C[P[i]].first;
int l=P[P[i]]+1, r=P[i];
dp[i]=query(1, 1, N+M, l, r)+val;
dp[i]=min(dp[i], query(1, 1, N+M, l, l)-dp[l-1]+dp[l]+val);
update(1, 1, N+M, l, P[i]-(i-P[i]), -(C[r+1].first-C[r].first));
ll t=C[Q[i]].first*(Q[i]-i+1)-(D[Q[i]]-D[i-1])+dp[i-1]+(Q[i]-i)*(C[Q[i]+1].first-C[Q[i]].first);
update2(1, 1, N+M, i, t);
}
return dp[N+M];
}
