#include <iostream>
#include <algorithm>
#include "wiring.h"
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
ll INF=1e18;
int N,M,K;
ll A[100005],B[100005];
vector<pll> W;
vector<ll> DP[100005],V[100005],R[2][100005];
ll D,res,ans;
void insert(int k, int l, int r, int t, int g, int j, ll a){
if(j<l or j>r)return;
if(l==r)R[t][g][k]=a;
else{
int m=(l+r)/2;
insert(2*k,l,m,t,g,j,a);
insert(2*k+1,m+1,r,t,g,j,a);
R[t][g][k]=min(R[t][g][2*k],R[t][g][2*k+1]);
}
}
void inserisci(int g, int j, ll a){
//cout<<"inserisci "<<g<<" "<<j<<" "<<a<<endl;
insert(1,0,DP[g].size(),0,g,j,a);
insert(1,0,DP[g].size(),1,g,j,a-((ll)DP[g].size()-j-1)*(V[g+1][0]-V[g][DP[g].size()-2]));
/*
R[0][g][j]=a;
R[1][g][j]=a-((ll)DP[g].size()-j-1)*(V[g+1][0]-V[g][DP[g].size()-2]);
*/
}
ll query(int k, int l, int r, int t, int g, int a, int b){
if(b<l or r<a)return INF;
if(a<=l and r<=b)return R[t][g][k];
int m=(l+r)/2;
return min(query(2*k,l,m,t,g,a,b),query(2*k+1,m+1,r,t,g,a,b));
}
ll minimo(int t, int g, int a, int b){
/*
ll res2=INF;
for(int i=a;i<b;i++)
res2=min(res2,R[t][g][i]);
*/
ll res=INF;
if(b<=a)
res=INF;
else
res=query(1,0,DP[g].size(),t,g,a,b-1);
//cout<<"minimo "<<t<<" "<<g<<" "<<a<<" "<<b<<" "<<res<<" "<<res2<<endl;
return res;
}
void stampa(){
for(int i=0;i<K;i++){
cout<<"gruppo "<<i<<endl;
for(ll g:DP[i])
cout<<g<<" ";
cout<<endl;
}
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
N=r.size();
M=b.size();
for(int a:r)
W.push_back({a,0});
for(int a:b)
W.push_back({a,1});
sort(W.begin(),W.end());
V[0].push_back(W[0].first);
DP[0].push_back(INF);
for(int i=1;i<N+M;i++){
if(W[i].second!=W[i-1].second)
K++;
V[K].push_back(W[i].first);
DP[K].push_back(INF);
}
K++;
for(int i=0;i<K;i++)
DP[i].push_back(INF);
for(int i=0;i<K;i++){
R[0][i].resize(4*DP[i].size(),INF);
R[1][i].resize(4*DP[i].size(),INF);
}
D=0;
for(int i:V[0])
D+=V[1][0]-i;
DP[0][0]=D;
inserisci(0,0,D);
for(int g=1;g<K-1;g++){
D=0;
for(int i:V[g])
D+=V[g+1][0]-i;
for(ll i=0;i<DP[g].size();i++){
res=INF;
res=min(res,minimo(0,g-1,0,(ll)DP[g-1].size()-i)+D);
res=min(res,minimo(1,g-1,max((ll)DP[g-1].size()-i,0LL),(ll)DP[g-1].size())+D+(V[g][0]-V[g-1][DP[g-1].size()-2])*i);
/*
for(int j=0;j<(int)DP[g-1].size()-i;j++)
res=min(res,DP[g-1][j]+D);
for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
res=min(res,DP[g-1][j]+D+(i-(ll)DP[g-1].size()+j+1)*(V[g][0]-V[g-1][DP[g-1].size()-2]));
*/
DP[g][i]=res;
inserisci(g,i,res);
if(i!=V[g].size()){
D-=V[g+1][0]-V[g][i];
D+=V[g][i]-V[g][0];
}
}
}
D=0;
for(int i:V[K-1])
D+=i-V[K-1][0];
ans=INF;
int g=K-1;
int i=(int)DP[g].size()-1;
for(int j=0;j<(int)DP[g-1].size()-i;j++)
ans=min(ans,DP[g-1][j]+D);
for(int j=max((int)DP[g-1].size()-i,0);j<DP[g-1].size();j++)
ans=min(ans,DP[g-1][j]+D+(i-(ll)DP[g-1].size()+j+1)*(V[g][0]-V[g-1][DP[g-1].size()-2]));
//stampa();
return ans;
}
/*
4 5
1 2 3 7
0 4 5 9 10
*/
/*
for(int i=0;i<K;i++){
cout<<"i "<<i<<endl;
for(int g:V[i])
cout<<g<<" ";
cout<<endl;
}
*/
